# NFA for all strings not containing 1010

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?

• 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. – Steven Oct 17 at 20:16
• 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. – D.W. Oct 17 at 20:49

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.