Prove or disprove the following statement: for arbitrary regular expressions $r_1$ and $r_2$ over an alphabet $\Sigma$ such that $\epsilon$ belongs to $L(r_1)$, there exists a regular expression $r$ over $\Sigma$ such that $r = r_1r + r_2$.

My Solution: Let us consider $\Sigma =\{a\}$. $L_1$ is even number of symbols so $r_1 =(aa)^*$ and $L_2$ is odd number of symbols so $r_2 = a(aa)^*$. $r$ is either $r_2$ which is possible or $rr_1$. Now if we keep replacing $r$ with $rr_1$ in the expression we will end up getting an infinitely large string because $r$ cannot be $\epsilon$ (thats what I think). So in my opinion this language is not regular. But I am not sure if I am thinking correctly.

  • 1
    $\begingroup$ The title of the post is too broad. Please take some time to improve it. $\endgroup$
    – fade2black
    Oct 16 '17 at 17:30
  • 3
    $\begingroup$ Look up Arden's rule. $\endgroup$ Oct 16 '17 at 18:00
  • $\begingroup$ What's the question here? This is not the right place to have your homework pre-graded. $\endgroup$
    – Raphael
    Oct 16 '17 at 18:47
  • $\begingroup$ $r=r_1r_2^{*}$ also works. $\endgroup$ Oct 17 '17 at 10:21

Take $r = (r_1 + r_2)^*$. We have to prove $$(r_1 + r_2)^* = r_1(r_1 + r_2)^* + r_2$$

First note that both $(r_1 + r_2)^*$ and $r_1(r_1 + r_2)^* + r_2$ contain $\epsilon$ since we are given that $\epsilon \in L(r_1)$, so we will consider a nonempty string in our proof.

Let's first show that $(r_1 + r_2)^*\subseteq r_1(r_1 + r_2)^* + r_2$. But it is trivial since we know that $\epsilon \in L(r_1)$ and so $$r_1(r_1 + r_2)^* + r_2 = (r_1 + r_2)^* + r_1'(r_1 + r_2)^* + r_2, \text { where } r_1 = r_1' + \epsilon$$

Now we have to show that $r_1(r_1 + r_2)^* + r_2 \subseteq (r_1 + r_2)^*$. Assume a nonempty string $s \in r_1(r_1 + r_2)^* + r_2$. Then either $s \in r_2$ or $s \in r_1(r_1+r_2)^m$ for some nonnegative integer $m$. In the first case since $r_2 \subseteq (r_1+r_2)^*$, we are done, so assume $s \in r_1(r_1+r_2)^m$. But we know that $(r_1+r_2)^{m+1} \subseteq (r_1+r_2)^*$. Thus $$(r_1+r_2)^{m+1} = (r_1+r_2)(r_1+r_2)^m = r_1(r_1+r_2)^m + r_2(r_1+r_2)^m$$ meaning $r_1(r_1+r_2)^m \subseteq (r_1+r_2)^*$.


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.