Solu tion
The conditions are
(a) the last two symbols can be ‘a’ or ‘b’.
(b) third symbol from the right is ‘a’
(c) symbol in any position but for the last three position can be ‘a’ or
‘b’.
The NFA is shown in fig. below.
Ì Exam ple 1.2.5: Sketch the NFA state diagram for
M
q q q q
q q
= ({ , , , }, { , }, , , { })
0
1
2
3
0
3
01 δ
with the state table as given below.
δ
0
1
q 0
q 0 , q 1
q 0 , q 2
q 1
q 3
∅
q 2
∅
q 3
q 3
q 3
q 3
Solu tion
The NFA states are q 0 , q 1 , q 2 and q 3 .
δ
δ
δ
δ
( , ) { , }
( , ) { }
( , ) { }
( , ) {
q
q q
q
q
q
q
q
q
0
0
1
1
3
3
3
0
0
0
0
0
1
=
=
=
=
, }
( , ) { }
( , ) { } .
q
q
q
q
q
2
2
3
3
3
1
1
δ
δ
=
=
The NFA is as shown below.
72
Theory of Automata, Formal Languages and Computation
q 0
q 1
q 2
q 3
a,b
a
a,b
a,b
q 1
q 2
q 0
q 3
1
0
0,1
0,1