Epsilon NFA to NFA

Converting an epsilon-NFA to an NFA is essential for simplifying and optimizing automata in real-world applications. Removing epsilon transitions reduces complexity, enhances efficiency, and makes the automaton easier to implement in computational systems.

• An epsilon-NFA (ε-NFA) is a type of non-deterministic finite automaton (NFA) where the automaton can transition between states without consuming any input symbol, called epsilon (ε) or empty transition.
• Non-deterministic Finite Automaton (NFA), the machine must consume input to transition between states. This is a key distinction from epsilon-NFA (ε-NFA), where transitions can happen without consuming any input symbol

Epsilon NFA To NFA Conversion Algorithm

If an epsilon transition exists between any two states in an automaton, the process of removing this epsilon transition through specific rules is referred to as the elimination of epsilon from the epsilon-NFA.

For example, let’s consider two states, V1 and V2, with an epsilon transition connecting them.

Here are the steps for eliminating epsilon transitions from an epsilon NFA 

• Step 1: Select the epsilon transition between two states. Label the vertices as V1 (the start of the epsilon transition) and V2 (the end of the transition) where the epsilon exists.
• Step 2: Identify all edges starting from V2. Simply duplicate the edges of V2 to V1 while maintaining the same labels. Then, remove the epsilon.
• Step 3: If V1 is the initial state, then V2 should be the initial state. If V2 is the final state, then V1 should be the final state. Remove any unreachable states, if they exist.
• Step 4: Check for any remaining epsilons. Repeat steps 1 to 3 until no epsilons are left.

Important Points !! Point 1: If multiple epsilon transitions exist in the epsilon-NFA, first remove the epsilon transition that is far away from the initial state. Point 1: An unreachable state cannot be reached from the initial state against any input.

Let’s discuss various examples based on the steps for eliminating epsilon from an NFA.

Example 01: Convert Epsilon NFA to NFA 

Consider the following epsilon NFA

Step 01: Find Epsilon Location

Epsilon exists between q0 and q1. So, q0  becomes V1 and q1 becomes V2.  Now apply the steps of epsilon removal.

Step 02:  Find starting edges from V2, duplicate it to V1, Remove Epsilon

Two edges are starting from V2 (q1)

• First Edge: Goes to q1 for input “b”.
• Second Edge: Goes to q1 again for input “c”.

Simply, duplicate these edges (starting from V2) to V1 and remove the epsilon edge.

Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q0) is the initial state. So V2(q1) becomes initial as well.

• Final state condition: As V2 (q1) is a final state. So V1(q0) also becomes the final state.

• Unreachable state condition: There is no unreachable state. So we cannot remove any state from the above NFA

Step 04: Check for any more Epsilon

Only the single epsilon was given in the example, which had already been removed. So, the final NFA is given below

Example 02: Convert Epsilon NFA to NFA 

Consider the following epsilon NFA

Step 01: Find Epsilon Location

Epsilon exists between q1 and q2. So, q1  becomes V1 and q2 becomes V2.  Now apply the steps of epsilon removal.

Step 02:  Find starting edges from V2, duplicate it to V1, Remove Epsilon

Only the single edge starts from V2 (q2) and goes to itself (q2) for input “b”. Simply, duplicate this edge (starting from V2) to V1 and remove the epsilon edge.

Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q1) is not the initial state. So, V2(q2) cannot be the initial state.

• Final state condition: As V2 (q2) is a final state. So V1(q1) also becomes the final state.

• Unreachable state condition: There is no unreachable state. So we cannot remove any state from the above NFA

Step 04: Check for any more Epsilon

Only the single epsilon was given in the example, which had already been removed. So, the final NFA is given below

Example 03: Convert Epsilon NFA to NFA 

Consider the following epsilon NFA

Step 01: Find Epsilon Location

Epsilon exists between q1 and q2. So, q1  becomes V1 and q2 becomes V2.  Now apply the steps of epsilon removal.

Step 02:  Find starting edges from V2, duplicate it to V1, Remove Epsilon

Only the single edge starts from V2 (q2) and goes to itself (q3) for input “b”. Simply, duplicate this edge (starting from V2) to V1 and remove the epsilon edge.

Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q1) is not the initial state. So V2(q2) cannot be the initial. 
• Final state condition: As V2 (q2) is not the final state. So V1(q1) cannot be the final state.
• Unreachable state condition: state “q4” is the unreachable state. So we remove this state from the above NFA

Step 04: Check for any more Epsilon

Only the single epsilon was given in the example, which had already been removed. So, the final NFA is given below

Example 04: Convert Epsilon NFA to NFA 

Consider the following epsilon NFA

Step 01: Find Epsilon Location

Epsilon exists between q2 and q3. So, q2  becomes V1 and q3 becomes V2.  Now apply the steps of epsilon removal.

Step 02:  Find starting edges from V2, duplicate it to V1, Remove Epsilon

Two edges are starting from V2 (q3)

• First Edge: Goes to q3 for input “a”.
• Second Edge: Goes to q3 for input “b”.

Simply, duplicate these edges (starting from V2) to V1 and remove the epsilon edge.

Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q2) is not the initial state. So V2(q3) cannot be the initial state.

• Final state condition: As V2 (q3) is a final state. So V1 (q2) also becomes the final state.

• Unreachable state condition: There is no unreachable state. So we cannot remove any state from the above NFA

Step 04: Check for any more Epsilon

Only the single epsilon was given in the example, which had already been removed. So, the final NFA is given below

 

Example 05: Convert Epsilon NFA to NFA 

Consider the following epsilon NFA

Step 01: Find Epsilon Location

In the above epsilon NFA,  there are two epsilons.

• First, Epsilon exists between q0 and q1.
• Second Epsioln exists between q1 and q2.

First, we remove the second epsilon, because it is far away from the initial state.

Step 02:  Find starting edges from V2, duplicate it to V1, Remove Epsilon

Only single edges start from V2 (q2) and go to q2 for input “c”. Simply duplicate this edge V1 (q1) and remove the epsilon edge with its label. We get the following

Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q1) is not an initial state. So V2(q4) cannot be an initial state; NFA remains unchanged.
• Final state condition: As V2 (q2) is a final state. So V1(q1) will be a final state. 

• Unreachable state condition: A constructed NFA has no unreachable state. 

Step 04: Check for any more Epsilon

Yes, still there exists one more epsilon edge between “q0” and “q1”. So, repeat the first 3 steps to remove the remaining epsilons.

Again, step 1: Find Epsilon Location

Epsilon exists between q0 and q1. So, q0  becomes V1 and q1 becomes V2.  Now apply the steps of epsilon removal.

Again, step 02:  Find starting edges from V2, duplicate it to V1, and Remove Epsilon

Two edges are starting from V2 (q1)

• First Edge: Goes to q1 for input “b”.
• Second Edge: Goes to q2 for input “c”.

Simply, duplicate these edges (starting from V2) to V1 and remove the epsilon edge.

Again, Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q0) is an initial state. So V2(q1) becomes initial as well. As given below

• Final state condition: As V2 (q1) is a final state. So V1(q0) will be a final. 

• Unreachable state condition: There is no unreachable state. So we cannot remove any state from the above NFA

Again, step 04: Check for any more Epsilon

As there were two epsilons given initially in the example, both are removed. No more epsilon exists.

Final Result:

So the final NFA, after removing all epsilons from the given epsilon NFA, is given below

Example 06: Convert Epsilon NFA to NFA 

Consider the following epsilon NFA

Step 01: Find Epsilon Location

In the above epsilon NFA,  there are two epsilons.

• First, Epsilon exists between q0 and q1.
• Second Epsioln exists between q1 and q2.

First, we remove the second epsilon, because it is far away from the initial state.

Step 02:  Find starting edges from V2, duplicate it to V1, Remove Epsilon

Only single edges start from V2 (q2) and go to q3 for input “a”. Simply duplicate this edge V1 (q1) and remove the epsilon edge with its label. We get the following

Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q1) is not an initial state. So V2(q4) cannot be an initial state; NFA remains unchanged.
• Final state condition: As V2 (q4) is not a final state. So V1(q1) cannot be a final state. NFA remains unchanged.
• Unreachable state condition: A constructed NFA has one unreachable state, which is q2. Simply remove this state along with its outgoing edges.

Step 04: Check for any more Epsilon

Yes, still there exists one more epsilon edge between “q0” and “q1”. So, repeat the first 3 steps to remove the remaining epsilons.

Again, step 1: Find Epsilon Location

Epsilon exists between q0 and q1. So, q0  becomes V1 and q1 becomes V2.  Now apply the steps of epsilon removal.

Again, step 02:  Find starting edges from V2, duplicate it to V1, and Remove Epsilon

Two edges are starting from V2 (q1)

• First Edge: Goes to q3 for input “a”.
• Second Edge: Goes to q3 for input “b”.

Simply, duplicate these edges (starting from V2) to V1 and remove the epsilon edge.

Again, Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q0) is an initial state. So V2(q1) becomes initial as well. As given below

• Final state condition: As V2 (q1) is not a final state. So V1(q0) cannot be a final. NFA remains unchanged
• Unreachable state condition: There is no unreachable state. So we cannot remove any state from the above NFA

Again, step 04: Check for any more Epsilon

As there were two epsilons given initially in the example, both are removed. No more epsilon exists.

Final Result:

So the final NFA, after removing all epsilons from the given epsilon NFA, is given below

 

Example 07: Convert Epsilon NFA to NFA 

Consider the following epsilon NFA

Step 01: Find Epsilon Location

In the above epsilon NFA,  there are three epsilons.

• First, Epsilon exists between q0 and q1.
• Second Epsioln exists between q1 and q5.
• Third Epsioln exists between q3 and q4.

First, we remove the third epsilon, because it is far away from the initial state.

Step 02:  Find starting edges from V2, duplicate it to V1, Remove Epsilon

Only single edges start from V2 (q4) and go to q5 for input “b”. Simply duplicate this edge V1 (q3) and remove the epsilon edge with its label. We get the following

Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q1) is not an initial state. So V2(q4) cannot be an initial state; NFA remains unchanged.
• Final state condition: As V2 (q4) is not a final state. So V1(q1) cannot be a final state. NFA remains unchanged.
• Unreachable state condition: A constructed NFA has one unreachable state, which is q4. Simply remove this state along with its outgoing edges.

Step 04: Check for any more Epsilon

Yes, still there exist two more epsilon edges

• First, Epsilon exists between q0 and q1.
• Second Epsioln exists between q1 and q5.

So, repeat the first 3 steps to remove the remaining epsilons.

Again, step 1: Find Epsilon Location

Epsilon exists between q1 and q5. So, q1  becomes V1 and q5 becomes V2.  Now apply the steps of epsilon removal.

Again, step 02:  Find starting edges from V2, duplicate it to V1, and Remove Epsilon

Only single edges start from V2 (q5) and go to q5 for input “c”. Simply, duplicate this edge with its label to V1 (q1) and remove the epsilon edge.

Again, Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q1) is not an initial state. So V2(q5) can not be the initial state.
• Final state condition: As V2 (q5) is a final state. So V1(q1) will be a final state.

• Unreachable state condition: There is no unreachable state. So we cannot remove any state from the above NFA

Again, step 04: Check for any more Epsilon

Now, only a single epsilon exists between q0 and q1.

Once again, step 01: Find Epsilon Location

Epsilon exists between q0 and q1. So, q0  becomes V1 and q1 becomes V2.  Now apply the steps of epsilon removal.

Step 02:  Find starting edges from V2, duplicate it to V1, Remove Epsilon

Three edges start from V2 (q1)

• First Edge: Goes to q2 for input “a”.
• Second Edge: Goes to q3 for input “a”.
• Third Edge: Goes to q5 for input “c”.

Simply, duplicate these edges (starting from V2) to V1 and remove the epsilon edge.

Step 03: Check Initial, Final, and Unreachable State Conditions

• Initial state condition: As V1 (q0) is the initial state. So V2(q1) becomes initial as well.

• Final state condition: As V2 (q1) is the final state. So V1(q0) will be the final state.

• Unreachable state condition: There is no unreachable state because “q1” is now the starting state as well. So we cannot remove any state from the above NFA

Step 04: Check for any more Epsilon

As there were three epsilons given initially in the example, all are removed. No more epsilon exists.

Final Result:

So the final NFA, after removing all epsilons from the given epsilon NFA, is given below