I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):

Build a DFA that recognizes the following language knowing that E = {0, 1}, {w | w is any string except 11 and 111}.

My solution is:

enter image description here

Is that correct? Thanks.

  • $\begingroup$ Does it recognize any string except for 11 and 111? $\endgroup$
    – user253751
    Apr 8, 2022 at 11:32
  • $\begingroup$ @user253751 yes that seems to be the question, to me the DFA looks fine! $\endgroup$
    – Stecco
    Apr 8, 2022 at 11:47
  • 3
    $\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$
    – Nathaniel
    Apr 8, 2022 at 12:38

1 Answer 1


Initially build a finite automata of the language which generates only strings 11 and 111 And then by complementing the finite automata we will obtain the language which accepts all strings except 11 and 111 As we know that L(M)'=U-L(M)you can check the finite automata here


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.