2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Nov 17 '20 at 23:26
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.