Search code examples
stateautomatacomputation-theorynfaepsilon

Converting Epsilon-NFA to NFA

I'm having trouble understanding the process of converting an epsilon-NFA to a NFA, so I wondered if anybody could help me with it:

nfae

And the answer says:

nfa

The 0 in the new NFA has an A going to 1,2 and to 2. I figured this is because the 0 in the Epsilon NFA leads to 1 and 2 with an A (combined with an Epsilon). So why doesn't the 1,2 have an A-step going to 2, because in the Epsilon NFA the 1 has an A-step to 1 and 2?

Solution

  • Whenever you remove an ε from the NFA, you should be careful at the time of conversion for the direction of ε transition.

    In your case, the ε transition is from node 1 to node 2, which is an accept state. So, you need to consider all the incoming transitions to the state 1.

    Also, as {1} moves to {2} upon ε-transition, so 1 can also be reduced to {1,2} and it'll be an accept state. Check this question to know why this happens.

    So, for removal of ε-transition, check all the incoming transitions to state 1, replace {1} with accept state {1,2} and convert them :-

    1. State 0 transits to state 1 when it reads a, and state 1 will automatically transit to state 2 as it reads ε.

    So, you should omit this path from 1 to 2(of ε-transition), and say that state 0 on reading a transits to both {1} and {2}. So, only 1 transition will be added to the exisitng NFA as 

    {0} -> {2} (on reading a)    // should be drawn, not given
{0} -> {1} (on reading a)    // this is already given
    1. State 2 transits to state 1 when it reads a, and state 1 will automatically transit to state 2 as it reads ε.

    So, you should omit this path from 1 to 2(of ε-transition), and say that state 2 on reading a transits to both {1} and {2}, itself. So, only 1 transition will be added to the exisitng NFA as 

    {2} -> {2} (on reading a)    // a self-loop, should be drawn, not given
{2} -> {1} (on reading a)    // this is already given

    Please take special care that you replace the state {1} with the accept state {1,2} because of the reason explained above.

    There are no more incoming arrows directed to state 1 and hence all the dependencies are resolved. The new NFA matches your given NFA as the answer.