1
$\begingroup$

A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current character being read.

If the machine halts when it's in an accepted state and at the same time the whole input has been consumed the input string is considered to be accepted.

Now, when introduce $\epsilon$ transitions the machine doesn't necessarily halt when the whole input string has been consumed, for it is possible that there are still $\epsilon$ transitions available.

Suppose we have a NFA that is in an accepted state and also that the whole input has been consumed, but there are still $\epsilon$ transitions available in this state, can we considered the input string to be accepted or do we need to "follow the trail" of $\epsilon$ transitions until we reach a state where no other transition is available?

$\endgroup$
0
$\begingroup$

One issue is that the way you're using the English language is appropriate for talking about DFAs but not appropriate for NFAs.

With a DFA, we can say "the DFA is in state $q$ after reading the input". That is well-defined for a DFA.

That is not well-defined for NFAs. There may be multiple possible runs, each of which ends in a different state. So it doesn't make sense to say "the NFA is in an accepting state after reading the whole input", because there may be multiple possible runs, some of which are in an accepting state and some of which are not.

The formal definition of a NFA gives a precise definition of under what conditions a string is considered to be accepted. Please consult any good textbook. The short answer to your last question is yes, the input string is accepted in that situation, as there exists a run of the NFA that ends in an accepting state and where the whole input has been consumed. But there's little point in us repeating material that's already covered in standard textbooks, and if you work through the definitions, you should be able to figure this out for yourself.

| cite | improve this answer | |
$\endgroup$

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.