Mathematical Foundation of Computer Science

DHARM

EQUIVALENCE OF NFA AND DFA 203

And the transition diagram for NFA is shown in Fig. 8.10.

0, 1

q 0 1, 2

q 1

q 2

0, 1, 2

2

0

1

Fig. 8.10

8.3.5 Equivalence of ‘NFA with ∈-moves’ to DFA

We have seen that automaton ‘NFA with ∈-moves’ is an extension of an NFA (in terms of
flexibility). Since, in the previous section, theorem 8.2 we have proved the equivalence be-
tween NFA with ∈-moves and NFA and the theorem 8.1 proves the equivalence between NFA
and DFA. Therefore, it concludes that, there exists an equivalence between NFA with ∈-moves
and the DFA a static nature of finite automata. This equivalence is shown in Fig. 8.11.

NFA with -moves

(N )

Î

Î

NFA (N)

DFA (M)

Fig. 8.11

Let N∈ = (Q∈, Σ, δ∈, {q 0 }∈, F∈), then construct an equivalent DFA M where M is defined

as,

M = (Q, Σ, δ, {q 0 }, F).

Now the relationship between corresponding tuples are as follows,

· Q ⊆ P (Q∈).

· Both automatons operate on same set of alphabet Σ.

· Starting state of DFA which is {q 0 } = ∈-closure{q 0 }∈. So, starting state of DFA will be

the set of state containing state {q 0 }∈.

· Set of final state F ⊆ Q, i.e. F ∩ F∈ ≠ Φ.

· Now we compute the transition functions δ for DFA over input symbol a (for ∀ a ∈ Σ)

as,

Let R = {q 1 , q 2 , ............qi} and ∪=

∀=j

i

1 δ( , ) { ,qa ppj^12 , ......pk}

Then, δ(R, a) = ∪ ∈-closure ({p 1 , p 2 , ......... pk})

Let us solve one example so that method will become more clear.