# When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?

The question is-: THIS is the transition table for NFA-: Final result as shown in youtube video. My question-: What are the final states of this nfa?

I think q0, q1 and q2 all are final states. Because $$\in$$ closure of q0,q1 gives q2. And q2 is the final state itself. So q2 U (q1 U q0) is the final state.

Another youtuber solves the same problem but gets different answer-: (exactly what I am telling and tbh this makes more sense than the first one) Then this neso academy video does the same (as I said).

In short your assumption: "I think q0, q1 and q2 all are final states." is true.

Suppose your $$\epsilon-\text{NFA}$$ is called $$M_1$$ and its equivalent $$\text{NFA}$$ is called $$M_2$$. every state in $$M_1$$ that can see at least one final state by only getting input $$\epsilon$$, will be a final state in $$\text{NFA}$$.

I think the reason will be quite obvious if you would consider $$q_1$$ in your own example of $$\epsilon-\text{NFA}$$.
A final state, $$q2$$, is in its $$\epsilon^{*}$$, i.e, being in state $$q_1$$ (after starting from the initial state and getting the input $$w$$) can end in $$q_2$$ and the given input will be accepted by $$M_1$$.
So in $$M_2$$ the state $$q_1$$ is a final state too (as long as $$q_0$$ with the same proof).

In the powerset construction $$2^{\mathcal{A}}$$ of an automaton $$\mathcal{A}$$, the final states of $$2^{\mathcal{A}}$$ are the sets that contain a final state of $$\mathcal{A}$$.

This also works when removing $$\varepsilon$$-transitions.

• I am not clear. Nov 12, 2021 at 15:29
• I just want to know final state of this NFA. Should not it be all states? Because all epsilon closure contains q2? Nov 12, 2021 at 15:33
• Yes, that's it. Nov 12, 2021 at 15:49