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

regex compiler-construction grammar automata
Prasoon Saurav picture Prasoon Saurav · Apr 17, 2010 · Viewed 15.7k times · Source

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?

Answer

RJFalconer picture RJFalconer · Apr 17, 2010

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

Related questions

Regular expressions - Matching whitespace

I am having a big problem to write a regexp that will trim all the whitespace in my input. I have tried \s+ and [ \t\t\r]+ but that don't work. I need this because I am writing a scanner …

Read More
Regular expression to match a line that doesn't contain a word

I know it's possible to match a word and then reverse the matches using other tools (e.g. grep -v). However, is it possible to match lines that do not contain a specific word, e.g. hede, using a regular …

Read More
How to validate an email address in JavaScript

Is there a regular expression to validate an email address in JavaScript?

Read More