Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 876
Prasoon Saurav Avatar asked Apr 17 '10 09:04

Prasoon Saurav


1 Answers

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

like image 64
RJFalconer Avatar answered Sep 26 '22 18:09

RJFalconer