Regular expression of the strings over {1,0} where all 11 occur before all 00

Question

I need to find a regular expression of the strings over {1,0} where all 11 occur before all 00.

I found the case where there is no 00's and where a 11 has to occur before a 00.

But I can't figure out how to make all 11's occur before all 00's

Answer 1

This works:

$$1^{*}(011^{*})^{*}(00^{*}1)^{*}0^{*}$$

Answer 2

The regexp is the concatenation of two sub-regexps:

1. The first part has no 00.
2. The second has no 11.

To generate the first part, i.e. the regexp of the language without consecuting zeros, we can consider: this language has at least one long of series of 1s, separated with zeros:

$$(0+\epsilon)((11^\star)0)^\star(\epsilon+11^\star)$$

In human language:

• we start with a 0 or with an empty string
• then we have at least 1 long list of 1s, suffixed with a single zero, 0 to infinite times
• finally we may stop with yet another at least 1 long list of 1s.

For the second part, the double 1-less language, we do the same, the result is

$$(1+\epsilon)((00^\star)1)^\star(\epsilon+00^\star)$$

Thus, the formula is

$$(0+\epsilon)((11^\star)0)^\star(\epsilon+11^\star)(1+\epsilon)((00^\star)1)^\star(\epsilon+00^\star)$$

Of course we could minimize it by converting it to a finite automata, then minimizing this automata, and then generate its regexp.