This is the question:

1.7. Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}.

a. The language {w| w ends with 00} with three states

This is how my professor answered it:

my professor answer

But this is the answer I found on web:

answer on web

But I think the second one should be the correct answer.


1 Answer 1


The first answer is incorrect. The automaton does not accept, for example, the input word $0100$. In fact, the first automaton misses at least all words in the language that are not of the form $1^*0^*$.

The second answer is correct. It is not hard to prove it. Can you try?


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.