Σ =
=
=
{ , }
a b
q
F
0
Initial state
Final state
We choose three states q 0 , q 1 , q 2 . The states count the number of b’s modulo 3,
with q 0 as the input as well as accepting state where q 1 and q 2 are not accepting
states. Run arrows from q 0 to q 1 , q 1 to q 2 and q 2 to q 0 with label ‘b’.
If any a is encountered, it does not alter the state. The suitable DFA is as
shown in the figure (a).
The state table diagram is shown in Fig. (b).
δ
a
b
q 0
q 0
q 1
q 1
q 1
q 2
q 2
q 2
q 0
Fig. (b) State table dia gram
Ì Exam ple 1.1.11: Construct an FA accepting all strings in {0,1}
* having
even number of 0’s.
Solu tion
The Finite Automaton M is given by
M q q q
q q
({ , , }, { , }, , , { }).
0
1
2
0
2
01 δ
The Finite Automaton is as shown.
66
Theory of Automata, Formal Languages and Computation
q 2
q 1
q 0
b
a
a
b
b
a
Fig. (a) DFA
q 1
q 0
q 2
0
1
0
1