1
$\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 '19 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 '19 at 20:49
2
$\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$
0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\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.