Home Â» Automata Eliminating null Transitions

# Eliminating Îµ Transitions

NFA with Îµ can be converted to NFA without Îµ, and this NFA without Îµ can be converted to DFA. To do this, we will use a method, which can remove all the Îµ transition from given NFA. The method will be:

1. Find out all the Îµ transitions from each state from Q. That will be called as Îµ-closure{q1} where qi âˆˆ Q.
2. Then Î´â€™ transitions can be obtained. The Î´â€™ transitions mean a Îµ-closure on Î´ moves.
3. Repeat Step-2 for each input symbol and each state of given NFA.
4. Using the resultant states, the transition table for equivalent NFA without Îµ can be built.

### Example:

Convert the following NFA with Îµ to NFA without Îµ.

Solutions: We will first obtain Îµ-closures of q0, q1 and q2 as follows:

Now the Î´â€™ transition on each input symbol is obtained as:

Now the Î´â€™ transition on q1 is obtained as:

The Î´â€™ transition on q2 is obtained as:

Now we will summarize all the computed Î´â€™ transitions:

The transition table can be:

Statesab
â†’q0{q1, q2}Ð¤
*q1Ð¤{q2}
*q2Ð¤{q2}

State q1 and q2 become the final state as Îµ-closure of q1 and q2 contain the final state q2. The NFA can be shown by the following transition diagram: