If a finite automata is modified to permit transitions without input symbols, along with zero, one, or more transitions on the input symbols, then we get an NFA with ‘∈-moves,’ because the transitions made without symbols are called "∈-transitions."

Consider the NFA shown in Figure 1.

Figure 1: Finite automata with ∈-moves.

This is an NFA with ∈-moves because it is possible to transition from state q_{0} to q_{1} without consuming any of the input symbols. Similarly, we can also transition from state q_{1} to q_{2} without consuming any input symbols. Since it is a finite automata, an NFA with ∈-moves will also be denoted as a five-tuple:

where Q, Σ, q_{0}, and F have the usual meanings, and δ defines a mapping from

(to take care of the ∈-transitions as well as the non ∈-transitions).

Acceptance of a String by the NFA with ∈-Moves

A string x in Σ* will ∈-moves will be accepted by the NFA, if at least one path exists that corresponds to x starts in an initial state and ends in one of the final states. But since this path may be formed by ∈-transitions as well as non-∈-transitions, to find out whether x is accepted or not by the NFA with ∈-moves, we must define a function, ∈-closure(q), where q is a state of the automata.

The function ∈-closure(q) is defined follows:

∈-closure(q)= set of all those states of the automata that can be reached from q on a path labeled by ∈.

For example, in the NFA with ∈-moves given above:

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

∈-closure(q_{1}) = { q_{1}, q_{2}}

∈-closure(q_{2}) = { q_{2}}

The function

∈-closure (q) will never be an empty set, because q is always reachable from itself, without dependence on any input symbol; that is, on a path labeled by ∈, q will always exist in ∈-closure(q) on that labeled path.

If P is a set of states, then the ∈-closure function can be extended to find ∈-closure(P ), as follows:

Algorithm for Finding ∈-Closure(q)

Let T be the set that will comprise ∈-closure(q). We begin by adding q to T, and then initialize the stack by pushing q onto stack:

while (stack not empty) do { p = pop (stack) R = δ (p, ∈) for every member of R do if it is not present in T then { add that member to T
push member of R on stack } }

Since x is a member of Σ*, and there may exist zero, one, or more transitions from a state on an input symbol, we define a new transition function, δ_{1}, which defines a mapping from 2^{Q} � Σ* to 2^{Q}. If x is written as wa, where a is the last symbol of x and w is a string made of remaining symbols of x then:

since δ_{1} defines a mapping from 2^{Q} � Σ* to 2^{Q}.

such that P contains at least one member of F and:

For example, in the NFA with ∈-moves, given above, if x = 01, then to find out whether x is accepted by the automata or not, we proceed as follows:

Therefore:

∈-closure(δ_{1} (∈-closure (q_{0}), 01) = ∈-closure({q_{1}}) = {q_{1}, q_{2}} Since q_{2} is a final state, x = 01 is accepted by the automata.

Equivalence of NFA with ∈-Moves to NFA Without ∈-Moves

For every NFA with ∈-moves, there exists an equivalent NFA without ∈-moves that accepts the same language. To obtain an equivalent NFA without ∈-moves, given an NFA with ∈-moves, what is required is an elimination of ∈-transitions from a given automata. But simply eliminating the ∈-transitions from a given NFA with ∈-moves will change the language accepted by the automata. Hence, for every ∈-transition to be eliminated, we have to add some non-∈-transitions as substitutes in order to maintain the language's acceptance by the automata. Therefore, transforming an NFA with ∈-moves to and NFA without ∈-moves involves finding the non-∈-transitions that must be added to the automata for every ∈-transition to be eliminated.

Consider the NFA with ∈-moves shown in Figure 2.

Figure 2: Transitioning from an ∈-move NFA to a non-∈-move NFA.

There are ∈-transitions from state q_{0} to q_{1} and from state q_{1} to q_{2}. To eliminate these ∈-transitions, we must add a transition on 0 from q_{0} to q_{1}, as well as from state q_{0} to q_{2}. Similarly, a transition must be added on 1 from q_{0} to q_{1}, as well as from state q_{0} to q_{2}, because the presence of these ∈-transitions in a given automata makes it possible to reach from q_{0} to q_{1} on consuming only 0, and it is possible to reach from q_{0} to q_{2} on consuming only 0. Similarly, it is possible to reach from q_{0} to q_{1} on consuming only 1, and it is possible to reach from q_{0} to q_{2} on consuming only 1. It is also possible to reach from q_{1} to q_{2} on consuming 0 as well as 1; and therefore, a transition from q_{1} to q_{2} on 0 and 1 is also required to be added. Since ∈ is also accepted by the given NFA ∈-moves, to accept ∈, and initial state of the NFA without ∈-moves is required to be marked as one of the final states. Therefore, by adding these non-∈-transitions, and by making the initial state one of the final states, we get the automata shown in Figure 3.

Figure 3: Making the initial state of the NFA one of the final states.

Therefore, when transforming an NFA with ∈-moves into an NFA without ∈-moves, only the transitions are required to be changed; the states are not required to be changed. But if a given NFA with q_{0} and ∈-moves accepts ∈ (i.e., if the ∈-closure (q_{0}) contains a member of F), then q_{0} is also required to be marked as one of the final states if it is not already a member of F. Hence:

If M = (Q, Σ, δ, q_{0}, F) is an NFA with ∈-moves, then its equivalent NFA without ∈-moves will be M_{1} = (Q, Σ, δ_{1}, q_{0}, F_{1})

where δ_{1} (q, a) = ∈-closure(δ ( ∈-closure(q), a))

and

F_{1} = F∪ (q_{0}) if ∈-closure (q_{0}) contains a member of F

F_{1} = F otherwise

For example, consider the following NFA with ∈-moves:

where

δ

0

1

∈

q_{0}

{q_{0}}

φ

{q_{1}}

q_{1}

φ

{q_{1}}

{q_{2}}

q_{2}

φ

{q_{2}}

φ

Its equivalent NFA without ∈-moves will be:

where

δ_{1}

0

1

q_{0}

{q_{0}, q_{1}, q_{2}}

{q_{1}, q_{2}}

q_{1}

φ

{q_{1}, q_{2}}

q_{2}

φ

{q_{2}}

Since there exists a DFA for every NFA without ∈-moves, and for every NFA with ∈-moves there exists an equivalent NFA without ∈-moves, we conclude that for every NFA with ∈-moves there exists a DFA.