1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The mistake isn't due to the absence of nondeterminism, as Yuval explains below. Also an NFA simply allows for the possibility of nondeterministic moves, it doesn't require them. In other words, a DFA can always be considered as an NFA that just happens not to have any nondeterministic transitions. $\endgroup$ – Rick Decker Feb 13 '14 at 2:55
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So should interpret as when no transition is defined, then stop? I thought it would be stay in the same state and can take next input $\endgroup$ – user5507 Feb 13 '14 at 2:31
  • 2
    $\begingroup$ @user5507. Your first interpretation is the correct one. If there is no transition defined from a state on a given input, then execution comes to a crashing halt: there's no move defined in that situation. $\endgroup$ – Rick Decker Feb 13 '14 at 2:50
  • $\begingroup$ @user5507, just for contrast, if you took the second interpretation, the first NFA would accept any string with two zeroes somewhere in it - we would be just ignore the 1s whenever you see them and there's no transition. This should be obviously a not-very-useful interpretation (apart from being the wrong one). $\endgroup$ – Luke Mathieson Feb 13 '14 at 12:57

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.