Elimination of Epsilon (ε) From NFA

If the epsilon exists between any two states in automata, then the removal of epsilon through some rules is called elimination of epsilon move from NFA.

Suppose there are two vertices, V1 and V2; the epsilon between them is below.

Epsilon (ε) moves in NFA

Steps For Elimination Of Epsilon From NFA

  • Step 01: Find all edges starting from V2
  • Step 02: Remove the epsilon. All Finding edges from V2 are Duplicated to V1 without changing edge labels.
  • Step 03: if V1 is initial state, make V2 initial
  • Step 04: if V2 is final state, make V1 final
  • Step 05: Remove all dead states

Note: if more than one epsilon exists in epsilon-NFA, then first remove the epsilon that is far away from the initial state. After the Removal of one epsilon, remove the others till the removal of the epsilon is.

Example of Elimination Of Epsilon From NFA

Consider the following epsilon NFA

Example of elimination of epsilon from NFA

Solution

In the above epsilon NFA, suppose q0 is a V1 and q2 is V2 because epsilon exists between these two states. Now apply the steps of epsilon removal.

Step 01: Find all edges starting from V2

  • The first input, “0”, starts from V2 (q2) and goes to q3.
  • The second input, “1”, starts from V2 (q2) and goes to q4

Step 02: Remove the epsilon. And All Finding edges from V2 are Duplicated to V1 without changing edge labels.

Finding outgoing edges from V2 are “0” and “1”.

  • First, Input “0” is going to q3 from V2 (q2). So, the first duplicate will go from V1 (q0) to q3.
  • Second Input “1” is going to q4 from V2 (q2). So, the second duplicate will go from V1 (q0) to q4.

So, duplicated edges with their labels are given below

Example of elimination of epsilon from NFA (step 2)

Step 03: If V1 is initial state, make V2 also initial

As V1 (q0) is an initial. So V2(q2) changes to initial. As given below

Example of elimination of epsilon from NFA (step 3)

Step 04: if V2 is final state, make V1 final State

As V2 (q2) is a final state. So V1(q0) changes to the final state. As given below

Example of elimination of epsilon from NFA (step 4)

Step 05: Remove all dead states

An unreachable state is called a dead state. In the above NFA, there is no dead state. So, the final NFA after the removal of epsilon is given below.

Example of elimination of epsilon from NFA (step 5) final