Solu tion
From the given table for δ, the DFA is drawn, where q 2 is the only final state.
(It is to be noted that a DFA can “accept” a string and it can “recognize” a language.
Catch here is that “accept” is used for strings and “recognize” for that of a language).
It could be seen that the DFA accepts strings that has at least one 1 and an
even number of 0s following the last 1.
Hence the language L is given by
L = {w | w con tains at least one 1 and
an even num ber of 0s fol low the last 1}
where L = L(M) and M recognized the RHS of the equation above.
Ì Exam ple 1.1.3: Sketch the DFA given
(
)
M
q q
q q
= { , }, { , }, , , { }
1
2
1
2
01 δ
and δ is given by
δ
δ
( , )
( , )
q
q
q
q
1
1
2
1
0
0
=
=
and
δ
δ
( , )
( , )
q
q
q
q
1
2
2
2
1
1
=
=
Determine a Language L(M), that the DFA recognizes.
Solu tion
From the given data, it is easy to predict the schematic of DFA as follows.
Internal states = q 1 , q 2 .
Symbols = 0, 1.
Transition function = δ (as defined above in the given problem)
q 1 = Initial state
q 2 = Final state.
DFA and NFA
61
q 1
q 2
q 3
0
1
1
0
0,1
Fig. Finite Autom a ton hav ing three states.
q 1
q 2
0
1
1
0
Fig. State dia gram of DFA