Consider the language $$ L = \{ w : w \in {0,1}^* \text{ and } w \text{ doesn't contain } 0110 \text{ as a substring.} \} $$ What is a regular expression for this language?
I thought of $1(1)^*0(0)^*$. But this seemed to not contain any strings starting with $0$. If I do $1(1)^*0(0)^* | 0(0)^*1(1)^*$ then it can contain $0110$. How can I improve my answer to this question?
A string avoids $0110$ regardless of any initial or final $1$-runs, so we it suffices to consider strings starting and ending with $0$. We can write every such string as follows: $$ 0^{a_1} 1^{b_1} 0^{a_2} 1^{b_2} \cdots 0^{a_\ell}, $$ where $a_1,b_1,a_2,b_2,\ldots,a_\ell \geq 1$. This string avoids $0110$ if $b_i \neq 2$ for all $i$.
The following infinite regular expression corresponds to the above: $$ \epsilon + 0^+ + 0^+(1+111^+)0^+ + 0^+(1+111^+)0^+(1+111^+)0^+ + \cdots $$ Here the first summand corresponds to the edge case $\ell = 0$. We can describe all of these cases using a single regular expression as follows: $$ \epsilon + (0^+(1+111^+))^*0^+ $$ Bringing back the initial and final $1$-runs, this gives the following regular expression for your language: $$ 1^* + 1^*(0^+(1+111^+))^*0^+1^* $$ Using some case analysis, we can simplify this into $$ 1^*(0^+(1+111^+))^*0^*1^* $$
