Here any subset containing q 1 is the final state in DFA. This is shown as below.
Ì Exam ple 1.3.2: Given the NDA as shown in Fig. (a), with δ as shown in
Fig. (b).
a
b
q 0
{q 0 , q 1 }
∅
q 1
∅
{q 1 , q 2 }
q 2
∅
∅
Fig. (b)
Determine the equivalent DFA for the above given NDA.
Solu tion
Conversion of NDA to DFA is done through subset construction as shown in
the State table diagram below.
a
b
[q 0 ]
[q 0 , q 1 ]
∅
[q 0 , q 1 ]
[q 0 , q 1 ]
[q 1 , q 2 ]
[q 1 , q 2 ]
∅
[q 1 , q 2 ]
∅
∅
∅
DFA and NFA
77
q 0
q 1
a
q 2
b
a
b
Fig. (a)
[] q 0
[] q 1
[] q 0, q 1
a
b
b
∅
a
b
a
a
b