0
$\begingroup$

The question is-:

enter image description here

THIS is the transition table for NFA-:

enter image description here

Final result as shown in youtube video.

https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49

enter image description here

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)

enter image description here

Source-: https://www.youtube.com/watch?v=ce0xAcABOYw

Then this neso academy video does the same (as I said).

https://www.youtube.com/watch?v=WSGcmaHNBFM

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.