Mathematical Foundation of Computer Science

DHARM

EQUIVALENCE OF NFA AND DFA 205

δ({q 1 , q 2 }, 1) = ∈-closure [δ({q 1 , q 2 }, 1)]
= ∈-closure [δ(q 1 , 1) ∪ δ(q 2 , 1)]
= ∈-closure [q 1 ∪ Φ]
= ∈-closure [q 1 ]
= {q 1 , q 2 } ≡ B [A repeated state]
δ({q 1 , q 2 }, 2) = ∈-closure [δ({q 1 , q 2 }, 2)]
= ∈-closure [δ(q 1 , 2) ∪ δ(q 2 , 2)]
= ∈-closure [Φ ∪ q 2 ]
= ∈-closure [q 2 ]
= {q 2 } ≡ C [A repeated state]
Now compute transitions from the state {q 2 }.
δ(q 2 , 0) = δ($δ(q 2 , ∈), 0)
= ∈-closure [δ( {q 2 }, 0)]
= ∈-closure [ Φ ]
= Φ;
δ(q 2 , 1) = δ(δΛ(q 2 , ∈), 1)
= ∈-closure [δ( {q 2 }, 1)]
= ∈-closure[Φ]
= Φ;
δ(q 2 , 2) = δ(δΛ(q 2 , ∈), 2)
= ∈-closure [δ( {q 2 }, 2)]
= ∈-closure [q 2 ]
= {q 2 } ≡ C [A repeated state]
Further we haven’t got any new state so procedure stops and we obtain the transition
diagram of DFA that is shown in Fig. 8.12.

0

1

0, 1 0, 1, 2

A B

C F

(^22)
0
1
2
Fig. 8.12 DFA M.