# Regular language such that L(r) = L(r₁) L(r) ∪ L(r₂)

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.

• The title of the post is too broad. Please take some time to improve it. Oct 16 '17 at 17:30
• Look up Arden's rule. Oct 16 '17 at 18:00
• What's the question here? This is not the right place to have your homework pre-graded.
– Raphael
Oct 16 '17 at 18:47
• $r=r_1r_2^{*}$ also works. 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)^*$.