Regular expression to match string of 0's and 1's without '011' substring

Question

I'm working on a problem (from Introduction to Automata Theory, Languages and Computer by Hopcroft, Motwani and Ullman) 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?

Editheditha

If you are giving up after an hour, I suggest you try harder and do some searching. – Laurentia

I'm not giving you the answer but try this: Draw a finite state machine (graph) that accepts 011 as an input and then negate it (all accepting states are none accepting and none accepting are accepting). You should be able to solve the regular expression from there as it also is a finite state machine. – Hawkins

Well that same trick works for that as well, Draw a finite state machine (graph) that accepts any string that contains 011 ... – Sajovich

Answer 1

Edit: Updated to include start states and fixes, as per below comments.

Audreaaudres

As you mentioned automata, I thought I'd draw some, as they're so fun! :). Both are deterministic finite state. I'll be happy to answer questions on their construction if they're not explanatory enough. (Or correct any mistakes). Hope this helps! – Audreaaudres

You have no arrow indicating the starting states! (-1 from the teacher) But we'll assume the leftmost shall we. The second is right on the money, the first is wrong. If you only accept exactly 011, all the arrows towards the leftmost state should go toward the righmost state in stead, because in those cases 011 can never be achieved any more. – Pilsen

Yes, you are correct. I have fixed the image. It would have previously rejected (some) strings that ended in 011. – Audreaaudres

I don't think your first graph is correct, when it reaches the last state, 011 will be accepted. – Sunstroke

@Sunstroke you're right; that's the machine for "all except exactly the string 011". The original question was unclear as to which the OP was looking for. The 2nd machine more closely matches the question as stands. – Audreaaudres

Can you also add a regular expression for this case – Purpure

Hey @PrasannaSasne; other answers have this already. What case are you looking for exactly? – Audreaaudres

I am looking for a regex for the same condition which you have implemented in DFA. – Purpure

Everything except 011? ^(?!(.*?011$)).*$ – Audreaaudres

Answer 2

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]*$

Freethinker

λ+0+1+00+01+10+11+(1+00+010)(0+1)* how did you reach to this RE? – Editheditha

The first part is an enumeration of all strings that are shorter than 3 chars. The second part are strings with which 011 can't start, followed by arbitrary data. – Freethinker

Your answer is wrong. 1*(0+01)* does not accept 10, nor does it accept 101. – Piquet

your answer 1*(0+01)* how it will not accept 011. can you please explain? – Purpure

@PrasannaSasne You can use regexr.com to explain the parts of the regex. In short, 1*(0+01)* does not match 011 as the only 1s it accepts are a 1 at the start (1* in the regex) or a 1 that is also prefixed by a 0 (the 01 in the (0+01)* regex) – Audreaaudres

Answer 3

Here is the regular expression:

0^* ∣1 + 0^∗ ∣0^* 01 + 0^*

Abstention

Answer 4

The simplest to code (and understand) is:

^(?!.*011)[10]*$

This is a negative look ahead (?!.*011) for the prohibited substring, and composed of 1's and 0's [10]* (change to [10]+ if blank is not a pass)

Pliant