Regular expression for a string not containing a set of substrings

Problem Detail: 

I'm trying to figure out how to build a regular expression for a language that doesn't contain strings that contain $101$ or $001$. The alphabet is defined as $\{0, 1\}$. I'm stuck on trying to figure out the DFA. Any help would be appreciated.

Asked By : flashburn

Answered By : J.-E. Pin

Hint. Let $A = \{0,1\}$. A regular expression for the complement of your language $L$ is $A^*(101 + 001)A^* = A^*A01A^*$. Now, as Shaull reminded you, $L$ and its complement have the same minimal complete DFA, up to the final states. It is actually relatively small.

If you prefer, you could also take a purely combinatorial approach. Observe that the strings you want to avoid are $101$ and $001$. It means that if a word $u$ of $L$ contains the pattern $01$, then $01$ has to be a prefix of $u$. Now find a regular expression for the set of words not containing the pattern $01$ and from there you should be able to find a regular expression for $L$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14837