0
$\begingroup$

enter image description here

Hello, Im new to learning epsilon nfas, and I have been wondering if we could leave certain epsilon transitions out, and if so would it still be a valid epsilon nfa? For example regarding the image, couldnt I just delete the marked epsilon transition and the state that it leads to, thus only having the unmarked epsilon and c transition left, and the states that they lead to? To me it seems that it is still equivalent to the epsilon nfa before deleting the marked transition, or does the marked epsilon transition have to exist?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, it has to exist. If you remove the circled $\epsilon$-transition, your resulting NFA will be different since the second state will become unreachable. You would only be able to accept the empty string whereas your actual NFA accepts either the empty string, or strings that contain only $c$'s.

In essence, the resulting NFA stays valid, but will not recognise the same language as the complete one.

$\endgroup$
4
  • $\begingroup$ Hello, thank u for ur answer. But couldnt I just delete the circled epsilon transition and the second state, and take a c tranisiton from the initial state directly to the third state? $\endgroup$
    – Seonix
    May 11, 2022 at 9:52
  • $\begingroup$ Yeah sure that will work too. But in that case, the $\epsilon$-transition to the accepting state would be useless. What you could do is a have a single starting state that is accepting, and do a loop on it that is used when recognising a $c$. $\endgroup$
    – seboll13
    May 11, 2022 at 10:05
  • $\begingroup$ Hi, but wouldnt the ϵ-transition to the accepting state be necessary, so words like cc, cccc can be accepted, I mean without it there would only be words like c and ϵ possible. $\endgroup$
    – Seonix
    May 11, 2022 at 12:57
  • $\begingroup$ @Seonix the goal of the loop is to avoid unnecessary $\epsilon$-transition. If you have a single accepting state with a loop for the character $c$ on it, then you will allow the empty string along with words with only $c$'s in it. In essence, your final NFA only has a single state which is accepting and a loop on it. $\endgroup$
    – seboll13
    May 11, 2022 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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