0
$\begingroup$

enter image description here

if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting state itself, right?

the starting state accepts 0,1 so I can essentially take the string 1010 and self loop it in the starting state itself... is that correct?

$\endgroup$
  • 1
    $\begingroup$ Your reasoning is correct.. but that shows that your NFA will actually accept the whole $\{0,1\}^*$... Remember that for a word to be accepted by a NFA, it is sufficient for one path leading to an accepting state to exist. To solve your problem it seems easier to just design a DFA. If you insist in having a NFA that is not a DFA, then just add a useless $\epsilon$-transition. $\endgroup$ – Steven Oct 17 at 20:16
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. $\endgroup$ – D.W. Oct 17 at 20:49
0
$\begingroup$

As mentioned in the comments, your NFA actually accepts all strings. What you have hit upon is the fact that NFAs are not resilient to complementation. Whereas given a DFA for a language, you can turn it to a DFA for the complement of the language by complementing the set of accepting states, the same doesn't hold for NFAs. In fact, "complementing" an NFA (that is, constructing an NFA for the complemented language) could result in exponential blow-up in the number of states!

As an example, consider the language of all words over $\{1,\ldots,n\}$ which do not contain all symbols. There is an NFA with $n$ states accepting the language (the NFA has multiple initial states, which might not be allowed under your definition), but any NFA for the complement must contain at least $2^n$ states. This blow-up is worst possible due to the powerset construction which converts an NFA with $n$ states to an equivalent DFA with $2^n$ states, which can be complemented without increasing the number of states.

$\endgroup$

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.