Regular Expression

Question

Ohh! this regular expression thing is eating my brain up. I have been reading it from Introduction to Automata Theory, Languages and Computer by Hopcroft, Motwani and Ullman.

I have solved a few exercises too but could not solve the following even after trying for almost one hr.

The problem is to write a regular expression that defines a language consisting of all strings of 0s and 1s not containing the substring 011.

Is the answer (0+1)^* - 011 correct ? If not what should be the correct answer for this?

EDITED

Answer 1

If you are looking for all strings that do not have 011 as a substring rather than simply excluding the string 011:

A classic regex for that would be:

1*(0+01)*

Basically you can have as many ones at the beginning as you want, but as soon as you hit a zero, it's either zeros, or zero-ones that follow (since otherwise you'd get a zero-one-one).

A modern, not-really-regular regex would be:

^((?!011)[01])*$

---

IF, however, you want any string that is not 011, you can simply enumerate short string and wildcard the rest:

λ+0+1+00+01+10+11+(1+00+010)(0+1)*

And in modern regex:

^(?!011)[01]*$

Answer 2