Mathematical Foundation of Computer Science

DHARM

EQUIVALENCE OF NFA AND DFA 195

Hence, we obtain the following transition Table (TT) for all possible states of DFA.

States

Input Symbols

01

ΦΦΦ

{q 0 }{q 0 , q 1 }{q 0 }

{q 1 } Φ {q 2 }

{q 2 }{q 3 } Φ

{q 3 }{q 3 }{q 3 }

{q 0 , q 1 }{q 0 , q 1 }{q 0 , q 2 }

{q 0 , q 2 }{q 0 , q 1 , q 3 }{q 0 }

{q 0 , q 3 }{q 0 , q 1 , q 3 }{q 0 , q 3 }

{q 1 , q 2 }{q 3 }{q 2 }

{q 1 , q 3 }{q 3 }{q 2 , q 3 }

{q 2 , q 3 }{q 3 }{q 3 }

{q 0 , q 1 , q 2 }{q 0 , q 1 , q 3 }{q 0 , q 2 , q 3 }

{q 0 , q 2 , q 3 }{q 0 , q 1 , q 3 }{q 0 , q 3 }

{q 1 , q 2 , q 3 }{q 3 }{q 2 , q 3 }

{q 0 , q 1 , q 3 }{q 0 ,q 1 , q 3 }{q 0 , q 2 , q 3 }

{q 0 , q 1 , q 2 , q 3 }{q 0 , q 1 , q 3 }{q 0 , q 2 , q 3 }

Fig. 8.2. TTDFA.
Note that all those states that contain {q 3 } as a state are considered as final states, these
states we marked with small circle along with the starting state {q 0 } which is marked with an
arrow.
Now, follow the procedure to construct the actual DFA from the TTDFA entries.
begin
from starting state
repeat
find new reachable state
until (while not found new reachable state)
end.
Applying the procedure we obtain a chain of reachable states from the starting state.
· From initial state {q 0 }, only reachable state are {q 0 , q 1 } and {q 0 } over input symbol 0
and 1 respectively. These are new reachable states so find next transitions from these
states.
· From state {q 0 , q 1 } reachable states are {q 0 , q 1 } and {q 0 , q 2 } on symbol 0 and 1. Since
state {q 0 ,q 1 } repeat itself so find next transitions from new reachable state {q 0 ,q 2 }.