0
$\begingroup$

I am reading in my book that this NFA machine accept the string 10100. If we follow the execution, we will find our self in branch with the state final q0.

The only answer for me is that when we are in state q0 after 1010 and 0 is coming we can't move any more so this branch will die even it is in the final state. Am I right?

enter image description here

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It doesn't, for exactly the reason you give. Why do you think it accepts? $\endgroup$
    – David Richerby
    Commented Feb 20, 2018 at 15:51
  • $\begingroup$ your answer is not clear. All i want is why this machine refuse the string 10100 $\endgroup$
    – mustafa salim
    Commented Feb 21, 2018 at 14:19
  • 2
    $\begingroup$ You have explained why the automaton rejects the string 10100. Your explanation is very simple and obviously correct. The book is clearly wrong. $\endgroup$
    – David Richerby
    Commented Feb 21, 2018 at 14:22

1 Answer 1

Reset to default
2
$\begingroup$

When a transition doesn't exist for current (state, input) pair, the NFA halts and the computation path rejects the input string. Or if an empty string transition is defined, it can be used to go into a garbage state for undefined transitions and the computation path rejects the string. See What does an NFA do if there's no transition with the correct symbol? for really good information.

In addition, this source that says the string is not accepted: http://people.cs.nctu.edu.tw/~wgtzeng/courses/FL2013SpringUnder/2.%20Finite%20automata.pdf slide 15.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Depend on your answer, even the machine in final state q0 and the the next input is 1 so their is no path to do something the machine will refuse the string. $\endgroup$
    – mustafa salim
    Commented Feb 21, 2018 at 14:23

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.