DHARMEQUIVALENCE OF NFA AND DFA 201
Similarly we can compute δ$(q 0 , 1) as,
δ$
∈(q 0 , 1) =
δ$
∈(q 0 , ∈. 1)
= δ∈($δ∈(q 0 , ∈), 1)
= ∈-closure [δ∈({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 }; [computed as previously]8.3.3 Language of NFA with ∈-moves........................................................................
In the previous section we have defined so far the nature of an NFA with ∈-moves over an
arbitrary string. Collection of all those strings over which ‘NFA with ∈-moves’ reaches to its
final state will be in its language set. Let LN∈ denotes the language of ‘NFA with ∈-moves’,
where LN∈ is defined as,
LN∈ = {x/x ∈Σ* and $δ∈(q 0 , x) ∩ F ≠ Φ}
Alternatively for an string x, which is formed over alphabet Σ will be in the language such that
while accepting the string x automaton is in the ∈-closure of state/s returned by $δ∈^ whose
intersection with the set of final states F will not be empty. Alternatively, δ$∈-head over x
returns at least one accepting state that is in final set of state F.
8.3.4 Method of Conversion from NFA with ∈∈∈∈∈-moves to NFA
Theorem 8.2. If N∈ be a NFA with ∈-moves, then there exists a NFA N (without ∈-moves) i.e.,
LN∈ = LN (where LN∈ is the language of N∈ and LN is the language of N)
Proof. Alternatively theorem states that, language of an NFA with ∈-moves is also the lan-
guage of an NFA without ∈-moves. To prove this statement let N∈ is defined as,
N∈ = (Q∈, Σ, δ∈, {q 0 }∈, F∈).
So, our objective is to construct an equivalent NFA N = (Q, Σ, δ, {q 0 }, F) from the known
N∈ such that,
l Q = Q∈, both automatons operate on same set of states.
l {q 0 } = {q 0 }∈, both automatons start operational on same state.
l F = F∈, set of all final state/s of NFA with ∈-moves must also be the final state/s of
NFA †.
l Both automatons operate on same set of alphabets that is Σ.
l Now we find the relationship between transition function δ∈ and δ over Σ.
Consider the same N∈ that is shown in Fig. 8.7, here Q∈ = {q 0 , q 1 , q 2 }, Σ = {0, 1, 2},
F∈ ={q 2 } and δ is given as follows:
q 0 Î q 1 Î q 20 1 2† F contains FU {q 0 } if ∈-closure (q 0 ) return a state from set F∈ otherwise F = F∈.