Question

Give a DFA/NFA to recognize L = { w | w contains exactly 2 a’s, 3 b’s and no c’s. Σ = {a,b,c} }

Answer 1

Easiest way to design FA for such problems is to draw 2 Finite Automata separately and then combine them.So this problem is related to the topic of composite Finite Automata

The given problem can be divided to 2 sub problems:

1) DFA with exactly 2 a's, any number of b's and no c's

2) DFA with exactly 3 b's, any number of a's and no c's

- போட்டு < b,C Da Dabc

D1 and D2 are representing the dead states in the above two DFA's.

Lets merge the above designed DFA together to get the required FA.

Note the start state is the combination of start state of both DFA's

i.e AW is the start state

The final state is the state where both the states are final. i.e CZ

Dead state: All the states containing atleast one of D1  or D2 represents the dead state ϕ.

STATE	a	b	c
AW	BW	AX	D1D2
AX	BX	AY	D1D2
AY	BY	AZ	D1D2
AZ	BZ	AD2	D1D2
BW	CW	BX	D1D2
BX	CX	BY	D1D2
BY	CY	BZ	D1D2
BZ	CZ	BD2	D1D2
CW	D1W	CX	D1D2
CX	D1X	CY	D1D2
CY	D1Y	CZ	D1D2
CZ	D1Z	CD2	D1D2

Lets rename the states of above state table for our convinience, and make the necessary changes.

ϕ is representing dead states in the below state table

STATE	a	b	c
q0	q4	q1	ϕ
q1	q5	q2	ϕ
q2	q6	q3	ϕ
q3	q7	ϕ	ϕ
q4	q8	q5	ϕ
q5	q9	q6	ϕ
q6	q10	q7	ϕ
q7	q11	ϕ	ϕ
q8	ϕ	q9	ϕ
q9	ϕ	q10	ϕ
q10	ϕ	q11	ϕ
q11	ϕ	ϕ	ϕ

Since in the problem we are asked to design a NFA or DFA we can remove the Dead state and simply draw the NFA.

The NFA with the above 12 states is shown below.

Please note that each state is representing different count of a's and b's

STATE	No of a's	No of b's
q0	0	0
q1	0	1
q2	0	2
q3	0	3
q4	1	0
q5	1	1
q6	1	2
q7	1	3
q8	2	0
q9	2	1
q10	2	2
q11	2	3

In case the problem was asking to design a DFA, you can also add a dead state and add all the ϕ transition which were shown in the state table above.