nfafinite-state-automaton

Is this NFA correctly accepting inputs that end with a 00?


In a lecture it was said that this NFA accepts inputs ending with two zeros or inputs=0: https://ibb.co/9Wt0j7J . The alphabet is {0,1}

But if the input would be 001 we would on some path also end up in the acceptance state (z2) but it would not be possible to go back to another state when reading the last character, the one. That would mean, a wrong input was accepted. So, my question is: Is the NFA really constructed correctly without changing anything? And if yes, why? Can I just assume that we go to an "empty (invisible) state (error state without mentioning it explicitly)" or something like that if there is no other arrow to another state?


Solution

  • Yes, it is a correct NFA for the given definition.

    But if the input would be 001 we would on some path also end up in the acceptance state (z2) but it would not be possible to go back to another state when reading the last character, the one. That would mean, a wrong input was accepted.

    If you put 001, it will not accept it since NFAs checks all possible paths and eliminates the paths which stuck. So you will go to z2 after the first two 0s but after reading the 1, it will stuck and be eliminated.

    Edit:

    ... an NFA accepts a string w if it is possible to make any sequence of choices of next state, while reading the characters of w and go from the start state to any accepting state.

    from the book Introduction to Automata Theory, Languages, and Computations by John E. Hopcroft, Rajeew Motwani, Jeffret D. Ullman, (2006, p.59).