Mathematical Foundation of Computer Science

DHARM

EQUIVALENCE OF NFA AND DFA 199

q p

Î

So it shows a spontaneous transition of state from state q to state p known as ∈-transi-
tion. This characteristic provides additional flexibility to the finite automaton. Hence, a finite
automaton with ∈ moves is more powerful than either from Nondeterministic or deterministic
finite automata.

8.3.1 Non Deterministic Finite Automata (NFA) with ∈ moves

A non deterministic finite automaton with ∈-moves is an extension of NFA. When some of the
transitions in the NFA are ∈-transitions such that, there are few transition/s of NFA are defined
over null string then NFA is called NFA with ∈-moves. It provides additional flexibility to the
NFA so that automaton skips between states spontaneously. Let N∈ be an NFA with-∈ moves,
whose tuples definition is given as,
N∈ = (Q, Σ, δ∈, {q 0 }, F)
where Q, Σ, {q 0 } and F holds similar meaning as an NFA and the transition function δ is
defined as follows,
δ∈ : Q × (Σ ∪ {∈}) → P(Q)
where, δ∈ is the partial mapping of a state with an input symbol including ∈ that returns to the
state that are in the power set of Q. As we said earlier, the transitions over ∈ are also known
as ∈- transitions.
For example, a NFA with ∈-moves is shown in Fig. 8.7 where set of states Q = {q 1 , q 2 , q 3 }
and set of alphabet Σ = {0, 1, 2}. The transition functions are shown in the TT Fig. 8.8.

q 0 Î q 1 Î q 2

(^012)
Fig. 8.7 NFA with ∈-moves.
States
Input symbols
Î
q 1
q 2
F
q
q
q
0
1
2
0
q 0
F
F
2
F
F
q 2
1
F
F
q 1
Fig 8.8 (TTNFA -∈ moves)

8.3.2 δ∈-head

As we discussed previously that transition function δ∈ gives the behavior of a ‘NFA with ∈-

moves’ over a single symbol including a null string (∈). Whereas, δ∈-head shows the nature of

NFA with ∈-moves over a string. We will now discuss the role of δ∈-head over various possible

strings, i.e.,

l If string is a null string ( ∈∈∈∈∈ ) then,

δ∈Λ (q, ∈) = {q} ∪{Set of all those states that can be reached from state q directly or

indirectly along any path whose transition/s are ∈-transition/s}

which is also called as ∈-closure (q);