World's most popular travel blog for travel bloggers.

[Solved]: Why the given NFA is not possible

, , No Comments
Problem Detail: 

I am trying to construct NFA for all languages ending in 00.

I got this

enter image description here

and this

enter image description here

First one I could convert to DFA by subset construction and I got the correct DFA. For the second one I got the DFA by subset construction, but it is not the correct one since it couldn't accept strings like 100.

Is this beacuse, there is no non determinism in the second NFA? Or what is the general rule in drawing an NFA? We could always provide some form of non determinism?

Asked By : user5507

Answered By : Yuval Filmus

The second NFA doesn't accept $100$. Make sure that you understand when an NFA accepts a given word. In this case, your NFA gets stuck at the very first character, since there is no transition labelled $1$ from the initial state.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21586

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback