Mathematical Foundation of Computer Science

DHARM

EQUIVALENCE OF NFA AND DFA 197

Sol. Let DFA be M, where M = {QD, Σ, δD, {q0D}, FD}. Now determine the tuples of M from
known tuples of N, as

States

Input Symbols

01

ΦΦΦ

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

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

{q 2 }{q 3 }{q 0 }

{q 3 } Φ {q 3 }

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

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

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

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

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

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

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

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

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

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

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

Fig. 8.5 TT.

· Now, QD ⊆ P(QNFA) or power set of states of NFA. Since QNFA = {q 0 , q 1 , q 2 , q 3 } hence

selection for QD from the set that contains 16 states including state Φ that are shown

in first column of TT (Fig. 8.4).

· Set of input symbol Σ = {0, 1}.

· Initial state of NFA is also the initial state of DFA, i.e., {q0D} = {q 0 }.

· FD ⊆ QD i.e., FD ∩ FN ≠ Φ.

· Now compute the transition functions δD over input symbols 0 and 1.

Since, all those states that contain either {q 1 } or {q 3 } are considered as final state/s of

DFA. So, mark those states with small circle. Now scan the TT from starting state

{q 0 }.

· Only reachable states from initial state are {q 1 , q 3 } and {q 1 } over the input symbols 0

and 1. Hence, find the next transitions from these states only.

· From state {q 1 , q 3 } the reachable states are {q 2 } and {q 0 , q 1 , q 2 } and from state {q 1 } the

only new reachable state is {q 1 , q 2 }.