Ì Exam ple 1.1.12: Construct a finite automaton accpting all strings over
{0, 1}
(a) having odd number of 0’s
(b) having even number of 0’s and even number of 1’s.
Solu tion
(a) M q q q
q q
({ , , }, { , }, , , { }).
0
1
2
0
1
01 δ
(See Fig. (a))
(b) M q q q q
q q
({ , , , }, { , }, , , { }).
0
1
2
3
0
0
01 δ
(See Fig. (b))
Ì Exam ple 1.1.13: Determine an FA, M accepting L,
where L w
= ∈
{
{ , } :
*
01 Every 0 in w has a 1 immediately to its right}.
Solu tion
The finite automaton is given by
M q q q q
q q
({ , , , }, { , }, , , { }).
0
1
2
3
0
2
01 δ
DFA and NFA
67
q 1
q 0
q 2
0
0
0
1
1
1
1
Fig. (a)
q 0
q 1
q 3
q 2
1
1
1
1
0
0
0
0
Fig. (b)
q 0
q 3
q 1
0
0
0,1
q 2
1
0
1