Mathematical Foundation of Computer Science

DHARM

200 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

For example, consider the NFA with ∈-moves shown in Fig. 8.7 so we can find,

∈-closure (q 0 ) = {q 0 } ∪ {q 1 , q 2 }

= {q 0 , q 1 , q 2 };

Similarly, ∈-closure (q 1 ) = {q 1 } ∪ {q 2 }

= {q 1 , q 2 };

and, ∈-closure (q 2 ) = {q 2 } ∪ Φ

= {q 2 };

· Assume a string x i.e., x ≠ ∈, then further assume that string x is form by a substring

‘y’ and a symbol ‘a’, i.e., x = y. a, then

δ$∈(q, x) = δ$∈(q, y. a) = δ∈(δ$∈(q, y), a);

or, δ$∈(q, x) = ∈-closure [δ∈($δ∈(q, y), a)]†; ...(1)

Thus, in general if P is the set of states, then

∈-closure (P) = ∀∈qP∪∈-closure (q) ...(2)

If string contains a single symbol ‘a’, then

δ∈ (P, a) = ∀∈∪q pδ∈(, )qa;

Similarly for a string x,

δ∈(P, x) = ∀∈∪q Pδ$∈(, );qx

If string contains a single symbol ‘a’ then,

δ$∈(q, a) = $δ∈(q, ∈.a) = δ∈(δ$∈(q, ∈), a)

= ∈-closure [δ∈(δ$∈(q, ∈), a]; ...(3)

For the NFA with ∈-moves shown in Fig. 8.7, $δ∈(q 0 , 0) can be computed as follows,

δ∈Λ(q 0 , 0) = δ∈Λ(q 0 , ∈ .0)

= δ∈(δ∈Λ(q 0 , ∈), 0)

= ∈-closure [δ∈({q 0 , q 1 , q 2 }, 0)]

= ∈-closure [δ∈(q 0 , 0) ∪ δ∈ (q 1 , 0) ∪ δ∈(q 2 , 0)]

= ∈-closure [{q 0 } ∪ Φ ∪ Φ]

= ∈-closure [{q 0 }]

= {q 0 , q 1 , q 2 }; [computed previously]

Note. If we compare the result obtained by δ∈ and δ$∈ on same symbol we find that, δ∈(q 0 , 0) = {q 0 }

and δ$∈(q 0 , 0) = { q 0 , q 1 , q 2 } so both are different. Hence, we conclude that, δ∈(q 0 , 0) ≠ δ$∈(q 0 , 0).

† Assume that, δ$∈(q, y) = {p 1 , p 2 , ..........pk} ∪ paths that may end with one or more ∈-transi-
tion/s from pi (for i = 1 to k)

let, ∪

∀=i ∈

k

1 δ (,)pai = {r^1 , r^2 , ......rm} ∪ {those states that can reach from rj by ∈-transition}

then, (^) δ$∈ (q, x) = ∪∈−
∀=j
m
1 closure r()j
Hence, $δ∈(q, x) = ∈-closure [δ∈ (δ$∈(q, y), a]