Regular expression of the strings over {1,0} where all 11 occur before all 00 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
 A: This works:
$$1^{*}(011^{*})^{*}(00^{*}1)^{*}0^{*}$$
A: The regexp is the concatenation of two sub-regexps:


*

*The first part has no 00.

*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.
