Mathematical Foundation of Computer Science

DHARM

206 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Example 8.3. Construct an equivalent DFA for given NFA with ∈-moves (Fig. 8.13).

A

Î Î

B D

C

0 0

0 1

Fig. 8.13

Sol. Let equivalent DFA M = (Q, Σ, δ, {q 0 }, F). So the tuples of M are obtain according as,
· Q ⊆ [Φ, {A}, {B}, {C}, {D}, {AB}, {AC}, AD}, {BC}, {BD}, {CD}, {ABC}, {ABD}, {BCD},
{ACD}, {ABCD}] which is a power set of Q∈.
· Σ = {0, 1}.
· Starting state of DFA is the ∈-closure (A) which is equal to {A, B, D}.
· All states of the set Q that contain {D} as one of the state are considered as final
states of DFA.
· Transition functions of DFA are as follows:
Find the ∈-closure of all the states, i.e., {A}, {B}, {C}, and {D}, i.e.,
∈-closure (A) = {A, B, D};
∈-closure (B) = {B, D};
∈-closure (C) = {C};
∈-closure (D) = {D};
Since, Starting state is {A, B, D}; so find δ over Σ from this state onwards,
δ({A, B, D}, 0) = δ({A, B, D}, ∈.0))

= ∈-closure [δ(δ$(A, ∈) ∪ (^) δ$(B, ∈) ∪ (^) δ$(D, ∈)), 0}]
= ∈-closure [δ( {A,B,D} ∪ {B,D} {D}), 0)]
= ∈-closure [δ({A,B,D}, 0) ]
= ∈-closure [δ(A, 0) ∪ δ(B, 0) ∪ δ(D,0)]
= ∈-closure [A ∪ C ∪ D]
= ∈-closure(A) ∪ ∈-closure(C) ∈ ∈-closure(D)
= {A,B,D} ∪ {C} ∪ {D}
= {A,B,C,D}; new state
δ({A, B, D}, 1) = ∈-closure [δ(A, 1) ∪ δ(B, 1) ∪ δ(D,1)]
= ∈-closure [Φ ∪ Φ ∪ Φ]
= ∈-closure (Φ)
= Φ;