Mathematical Foundation of Computer Science

DHARM

204 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Example 8.2. Construct a DFA from given NFA (as shown in Fig. 8.7)

q 0

Î

q 1

Î

q 2

0 1 2

Sol. For the given NFA with ∈-moves we assume that equivalent DFA M = (Q, Σ, δ, {q 0 }, F)
whose tuples are determine as,
· Q ⊆ [Φ, {q 0 }, {q 1 },{q 2 },{q 0 , q 1 },{q 0 , q 2 },{q 1 , q 2 }, {q 0 , q 1 , q 2 }] which is a power set of Q∈.
· Σ = {0, 1, 2}.
· Starting state of DFA is {q 0 } where, {q 0 } = ∈-closure (q 0 ) = {q 0 , q 1 , q 2 }.
· All states of the set Q that contains {q 2 } as one of the state are considered as final
state/s.
· The transition functions of DFA are determine as follows,
Since starting state is {q 0 , q 1 , q 2 } hence,
δ({q 0 , q 1 , q 2 }, 0) = δ(δΛ({q 0 , q 1 , q 2 }, ∈), 0)
= ∈-closure [δ∈( δ∈Λ(q 0 , ∈) ∪ δΛ(q 1 , ∈)δΛ(q 2 , ∈)), 0}]
= ∈-closure [δ( ({q 0 , q 1 , q 2 } ∪ {q 1 , q 2 } ∪ {q 2 }), 0)] [using ∈-closure property]
= ∈-closure [ δ({q 0 , q 1 , q 2 }, 0)]
= ∈-closure [δ(q 0 , 0) ∪ δ(q 1 , 0) ∪ δ(q 2 , 0)]
= ∈-closure [q 0 ∪ Φ ∪ Φ ] [from state diagram]
= ∈-closure[q 0 ]
= {q 0 , q 1 , q 2 } ≡ A (let) [A repeated state]
and δ({q 0 , q 1 , q 2 }, 1) = ∈-closure [δ(q 0 , 1) ∪ δ(q 1 , 1) ∪ δ(q 2 , 1)]
= ∈-closure [Φ ∪ q 1 ∪ Φ]
= ∈-closure [q 1 ]
= {q 1 , q 2 } ≡ B (let)
δ({q 0 , q 1 , q 2 }, 2) = ∈-closure [ δ(q 0 , 2) ∪ δ(q 1 , 2) ∪ δ(q 2 , 2)]
= ∈-closure [Φ ∪ Φ ∪ q 2 ]
= ∈-closure [q 2 ]
= {q 2 } ≡ C (let)
Now compute transitions from new state {q 1 , q 2 } and {q 2 } as,
δ({q 1 , q 2 }, 0) = δ(δΛ({q 1 , q 2 }, ∈), 0)
= ∈-closure [δ(δΛ(q 1 , ∈) ∪ δΛ(q 2 , ∈)), 0}]
= ∈-closure [ δ( ({q 1 , q 2 } ∪ {q 2 }), 0)]
= ∈-closure [δ({q 1 , q 2 }, 0)]
= ∈-closure [δ(q 1 , 0) ∪ δ(q 2 , 0)]
= ∈-closure [Φ ∪ Φ]
= Φ