DHARMEQUIVALENCE OF NFA AND DFA 207
δ({A, B, C,D}, 0) = ∈-closure [δ({A,B,C,D}, 0)]
= ∈-closure [δ(A, 0) ∪ δ(B, 0) ∪ δ(C, 0) ∪ δ(D, 0)]
= ∈-closure [ A ∪ C ∪ Φ ∪ D]
= ∈-closure (A) ∪ ∈-closure(C) ∪ ∈-closure (D)
= {A, B, D} ∪ {C} ∪ {D}
= {A, B, C, D}; a repeated state
δ({A, B, C,D}, 1) = ∈-closure[ δ({A,B,C,D}, 1)]
= ∈-closure [δ(A, 1) ∪ δ(B, 1) ∪ δ(C, 1) ∪ δ(D, 1)]
= ∈-closure [Φ ∪ Φ ∪ B ∪ Φ]
= ∈-closure (B)
= {B, D}; a new state
δ((B, D), 0) = ∈-closure [δ( {B, D}, 0)]
= ∈-closure [δ(B, 0) ∪ δ(D, 0)]
= ∈-closure [C ∪ D]
= ∈-closure (C) ∈-closure (D)
= {C, D}; a new state
δ((B, D), 1) = ∈-closure [δ( {B, D}, 1)]
= ∈-closure [δ(B, 1) ∪ δ(D, 1)]
= ∈-closure [ Φ ∪ Φ ]
= ∈-closure (Φ)
= Φ;
δ((C, D), 0) = ∈-closure [δ( {C, D}, 0)]
= ∈-closure [δ(C, 0) ∪ δ(D, 0)]
= ∈-closure [Φ ∪ D]
= ∈-closure (D)
= {D}; a new state
δ((C, D), 1 = ∈-closure [δ{C, D}, 1)]
= ∈-closure [δ(C, 1) ∪ δ(D, 1)]
= ∈-closure [B ∪ Φ]
= ∈-closure (B)
= {B,D}; repeated state
δ(D, 0) = ∈-closure [ δ(D, 0)]
= ∈-closure [D]
= {D}; a new state
δ(D, 1) = ∈-closure [δ(D, 1)]
= ∈-closure [Φ]
= Φ;
Further there is no new state generated so we stop the process and finally we obtain the
DFA shown in Fig. 8.14.