Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
From S with input 1, you can’t go both to state S and A. In states A, B, C where do you go with the other input? What happens in state D if you get further input?
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?
Your machine is not correct. The problem is as you pointed out: If you start in state $S$ of your machine, you can take the string 1010 and self-loop in the starting state. That shows that your machine accepts 1010, but you wanted to design a machine that does not accept 1010 :(
This is an example of a language that is hard to make an NFA for. Often, NFAs are easier than DFAs because they allow nondeterminism, but here an NFA will probably need just as many states as a DFA.
