# Regular expression for do not contain

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?

• Going through DFA is simple and fast method for your example. – sashas Nov 3 '15 at 22:35
• 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.) – D.W. Nov 3 '15 at 23:43

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