Mathematical Foundation of Computer Science

DHARM

202 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

The definition of transition functions δ for NFA (over each symbol of Σ) cover all the
definition of transition functions δ∈ for NFA with ∈-moves including ∈-transition/s. Since,
∈-transition/s can not be the part of δ for NFA; hence all ∈-transition/s arcs can be replaced by
either of the symbol of Σ. This is because, the flexibility of spontaneous skip between ∈-transi-
tion states over no symbol (∈)†. For example,

δ$∈(q 0 , 0) = δ$∈(q 0 , 0. ∈)
= δ∈(δ∈Λ(q 0 , ∈), 1)
= ∈-closure [δ∈Λ({q 0 , q 1 , q 2 }, 0)]; [applies ∈-closure pop.]
= ∈-closure [δ∈(q 0 –, 0) ∪ δ∈(q 1 , 0) ∪ δ∈(q 2 , 0)]
= ∈-closure [{q 0 } ∪ Φ ∪ Φ]
= ∈-closure [ {q 0 }] [computed previously]
= {q 0 , q 1 , q 2 };
Hence, we say that on symbol 0 the state of the automaton will be either {q 0 } or {q 1 } or
{q 2 }. That is the requirement of the NFA. So, transition function δ for NFA is given as,

δ(q 0 , 0) = δ$∈(q 0 , 0).
In general for any input symbol a ∈ Σ, we have
δδδδδ(q 0 , a) = δ$∈∈∈∈∈(q 0 , a)
It states that the behavior of both automatons N∈ and N are same on same input sym-
bol. Hence, It concludes that in general if LN∈ is the language of a N∈ then language of a NFA
N is also LN i.e.,
LN = LN∈
Hence, δ(q 0 , 0) = δ$∈(q 0 , 0) = {q 0 , q 1 , q 2 };
Similarly δ(q 0 , 1) = $δ∈(q 0 , 1) = {q 1 , q 2 };
δ(q 0 , 2) = δ$∈(q 0 , 2) = {q 2 }; and so on.
Therefore, the TT for NFA will be looks like, (Fig. 8.9)

Input symbol

State

q 0

q 1

q 2

0

{,,}qqq 012

F

F

02

{, }qq 12

{, }qq 12

F

{}q 2

{}q 2

{}q 2

Fig. 8.9 TTNFA.

† It explains how to remove ∈-transition/s from ‘NFA with ∈-moves’ so that it converts to NFA
(without ∈-moves).