The language is $\{w \mid \text{$w$ is any string except $11$ and $111$}\}$ where the alphabet is $\{0,1\}$.

Drawing the DFA recognizing $\{v \mid \text{$v$ is either $11$ or $111$}\}$, then switching the accept and non-accept states, and finally examining this resulting structure, I thought of it as being:


My reasoning was that it has to accept the empty string, or a 0 followed by whatever or just a $1$ or, if it begins with a $1$, a $10$ followed by whatever or, if it begins with $11$, then a $110$ followed by whatever or a $111$ followed by at least a $0$ or a $1$

Does this appear to be correct? If I'm wrong, could you please tell me why?

Thank you,

  • $\begingroup$ You could have written it more compactly, e.g. $\epsilon + 1 + (0 + 1(\epsilon + 1 + 11)0)(1 + 0)^*$, but the idea is basically the same. $\endgroup$
    – wvxvw
    Commented Sep 29, 2015 at 23:25
  • 4
    $\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. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Sep 29, 2015 at 23:28

2 Answers 2


Yes, your idea is correct.
Basically here two things are happening.

  1. Regular languages are closed under compliment operation
  2. If L1 is accepted by DFA1 and DFA2 is obtained by interchanging the final states to non-final states and non-final states to final states of DFA1 then the language accepted by DFA2 is compliment of L1. That is, if
    • DFA1 is a quintuple (Q, Σ, δ , q0, F)
      And L1 is language accepted by DFA1
    • DFA2 is (Q, Σ, δ , q0, (Q - F))
      And L2 is language accepted by DFA2

      Then L2 is compliment of L1.

In this case the languages
L1 = {w∣w is any string except 11 and 111} and L2 = {v∣v is either 11 or 111} are compliment o each other .
Hence your approach is correct.



  • 1
    $\begingroup$ I do not understand the parts repeated 3 or 4 times, respectively - (0+1)³ matches 111, (0+1)⁴ doesn't match 10101. $\endgroup$
    – greybeard
    Commented May 29, 2022 at 10:02
  • 2
    $\begingroup$ We're not looking for answers that are just a complex expression -- we are looking for answers that come with explanation, a description of the ideas, and/or a proof of correctness. Can you edit your answer accordingly? $\endgroup$
    – D.W.
    Commented May 30, 2022 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.