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
