1
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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