# Elimination of Epsilon (ε) From NFA

**
**If the epsilon exist between any two states in automata then the removal of epsilon through some rules is called

**elimination of epsilon**move form NFA.

Suppose there are two vertices V1 and V2 and epsilon between them is given below.

**Steps For Elimination Of Epsilon From NFA**

**Step 01:**Find all edges starting from V2**Step 02:****Remove the epsilon. And**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 are exist in epsilon-NFA, then first remove the epsilon which is far away from initial state. After Removal of one epsilon remove the others till the all removal of epsilon.

**Example of Elimination Of Epsilon From NFA**

Consider the following epsilon NFA

**Solution**

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

**Step 01:** Find all edges starting from V2

- The first input “0” is starting from V2 (q2) and going to q3.
- The second input “1” is starting from V2 (q2) and going to q3

**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 first duplicate will goes from V1 (q0) to q3.
- Second Input “1” is going to q4 from V2 (q2). So second duplicate will goes from V1 (q0) to q4.

So, duplicated edge with their labels are given below

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

As V1 (q0) is a initial. So V2(q2) change to initial. As given below

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

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

**Step 05: **Remove all dead states

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