Home » Automata Eliminating null Transitions

Automata Eliminating null Transitions

by Online Tutorials Library

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 ε.

Eliminating Null Transitions

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:

States a b
→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:

Eliminating Null Transitions


You may also like