Algorithms for Compiler Design: THE NFA WITH ∈-MOVES

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₀ to q₁ without consuming any of the input symbols. Similarly, we can also transition from state q₁ to q₂ 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₀, 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₀) = { q₀, q₁, q₂}

• ∈-closure(q₁) = { q₁, q₂}

• ∈-closure(q₂) = { q₂}

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, δ₁, 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 δ₁ 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(δ₁ (∈-closure (q₀), 01) = ∈-closure({q₁}) = {q₁, q₂} Since q₂ 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₀ to q₁ and from state q₁ to q₂. To eliminate these ∈-transitions, we must add a transition on 0 from q₀ to q₁, as well as from state q₀ to q₂. Similarly, a transition must be added on 1 from q₀ to q₁, as well as from state q₀ to q₂, because the presence of these ∈-transitions in a given automata makes it possible to reach from q₀ to q₁ on consuming only 0, and it is possible to reach from q₀ to q₂ on consuming only 0. Similarly, it is possible to reach from q₀ to q₁ on consuming only 1, and it is possible to reach from q₀ to q₂ on consuming only 1. It is also possible to reach from q₁ to q₂ on consuming 0 as well as 1; and therefore, a transition from q₁ to q₂ 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₀ and ∈-moves accepts ∈ (i.e., if the ∈-closure (q₀) contains a member of F), then q₀ 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₀, F) is an NFA with ∈-moves, then its equivalent NFA without ∈-moves will be M₁ = (Q, Σ, δ₁, q₀, F₁)

where δ₁ (q, a) = ∈-closure(δ ( ∈-closure(q), a))

and

• F₁ = F ∪ (q₀) if ∈-closure (q₀) contains a member of F

• F₁ = F otherwise

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

where

δ	0	1	∈
q0	{q0}	φ	{q1}
q1	φ	{q1}	{q2}
q2	φ	{q2}	φ

Its equivalent NFA without ∈-moves will be:

where

δ1	0	1
q0	{q0, q1, q2}	{q1, q2}
q1	φ	{q1, q2}
q2	φ	{q2}

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.