(b) Given L
ab n
B
n
=
≥
{( ) |
}
1 (∈-not accepted) i.e., initial state ≠ final state).
The FA for this language L B is shown in Fig. (b).
The FA is given by
M q q q q
a b
q q
({ , , , }, { , }, , , )
0
1
2
3
0
2
δ
where q 3 is a “dead state”.
Ì Exam ple 1.1.16: Determine the FA with the
(a) Set of strings beginning with an ‘a’.
(b) Set of strings beginning with ‘a’ and ending with ‘b’.
(c) Set of strings having ‘aaa’ as a subword.
(d) Set of integers
(e) Set of signed integers.
Solu tion
(a) Set of strings beginning with an ‘a’.
[It is not necessary always to have a dead state]
(b) Set of strings beginning with ‘a’ and ending with ‘b’.
DFA and NFA
69
q 3
q 0
q 1
a
a
b
a
b
q 2
b
a
b
Fig.(b)
q 3
q 0
a
b
a
b
q 1
q 2 b
a
b
a
q 2
q 0
a
b
a
b
q 1 a
b