What is regular expression for language that does not contain $1110$?

It is easy to guess for language that contains. The shortest way I know is go through DFA. Is there a better way?

  • 4
    $\begingroup$ Going through DFA is simple and fast method for your example. $\endgroup$ Nov 3, 2015 at 22:35
  • $\begingroup$ It's not clear what you would consider "better" -- you need to define "better", as that is subjective. It's not clear what you mean by "shortest" (shortest reg exp? shortest sequence of derivations? easiest for a human? most efficient for a computer?) To make the question well-posed, identify what property you want the alternative way to have (some property that going through a DFA doesn't have): why have you rejected "going through a DFA"? (See also our reference question, especially this answer.) $\endgroup$
    – D.W.
    Nov 3, 2015 at 23:43

1 Answer 1


One solution is $(0+10+110+1111^*0)^*1^*$.

However, I don't see how this helps you understand anything. It is much better for you to come up with the answer yourself. As an exercise, you can try proving that this expression indeed works correctly. (Or uncover any mistake, as the case may be.)


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.