Theory of Automata

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.

Epsilon (ε) moves in NFA

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

Example of elimination of epsilon from 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

Example of elimination of epsilon from NFA (step 2)

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

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) change to final state. As given below

Example of elimination of epsilon from NFA (step 4)

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

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

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest