δ′ is given by the following state table.
0
1
→ [ ]
q 0
[q 0 , q 1 ]
[q 0 , q 3 ]
[q 0 , q 1 ]
[ , , ]
q q q
0
1
2
[q 0 , q 3 ]
[q 0 , q 3 ]
[q 0 , q 1 ]
[ , , ]
q q q
0
3
4
[ , , ]
q q q
0
1
2
[ , , ]
q q q
0
1
2
[q 0 , q 3 ]
[ , , ]
q q q
0
3
4
[q 0 , q 1 ]
[ , , ]
q q q
0
3
4
Any state containing q 2 or q 4 will be a final state.
The DFA is shown below.
Ì Exam ple 1.3.4: Determine a NFA accepting {ab, ba} and use it to find
a DFA accepting it.
Solu tion
The state table is as shown below.
a
b
q 0
q 1
q 2
q 1
∅
q 3
q 2
q 3
∅
q 3
∅
∅
The NFA is shown below.
q 0 is the input state, q 3 is the final state.
DFA and NFA
79
[] q 0, q 3
[] q 0, q 1
[] q 0, q 12 ,q
[] q 0, q 34 ,q
0
0
1
1
0
1
0
1
[] q 0
q 0
q 1
q 2
q 3
a
a
b
b