# Regular expression for all binary strings avoiding 0110

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?

• One mechanical way to do it: Construct a DFA that recognizes $\overline{L}$. Complement the set of final states and construct the regular expression associated with the resulting DFA. Nov 17, 2020 at 23:26

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^*$$