The corresponding DFA is shown below. Please note that here any subset
containing q 2 is the final state.
Ì Exam ple 1.3.3: Given the NDA as shown in fig. below, determine the
equivalent DFA.
Solu tion
The given NDA has q 2 and q 4 as final states. It accepts strings ending in 00 or
11. The state table is shown below.
0
1
q 0
{q 0 , q 1 } {q 0 , q 3 }
q 1
{q 2 }
∅
q 2
∅
∅
q 3
∅
{q 4 }
q 4
∅
∅
The conversion of NDA to DFA is done through the subset construction.
78
Theory of Automata, Formal Languages and Computation
∅