4
$\begingroup$

I came across the following equality of regular expressions $$(r|s)^* = (r^*.s^*)^*\,,$$ where $r$ and $s$ are two regular expressions and $.$ denotes concatenation, but I don't know how could I prove it.

My try:

I call $L(r)$ the language defined by the regular expression $r$. And I want to use the fact that two regular expressions $r$ and $s$ are equal iff $L(r) = L(s)$.

The LHS can be writen as follows: $$ L((r|s)^{*}) = \bigcup_{i=0}^{+\infty} L(r|s)^{i} = \bigcup_{i=0}^{+\infty} (L(r)^{i} \cup L(s)^{i})\,. $$

The RHS can be writen as follows: $$ L((r^{*}.s^{*})^{*}) = \bigcup_{i=0}^{+\infty} L((r^{*}.s^{*}))^{i}\,.$$

But I got stuck at this point and I don't know how to proceed.

$\endgroup$
2
  • $\begingroup$ What is dot "." in the RHS of this equation? $\endgroup$ Apr 1, 2017 at 8:23
  • $\begingroup$ @Andremoniy Concatenation. $\endgroup$ Apr 1, 2017 at 8:25

2 Answers 2

6
$\begingroup$

In one direction, $$ L((r^*s^*)^*) \subseteq L(((r|s)^*(r|s)^*)^*) = L(((r|s)^*)^*) = L((r|s)^*). $$ In the other direction, $L(r) \subseteq L(r^*s^*)$ and $L(s) \subseteq L(r^*s^*)$ imply that $L(r|s) \subseteq L(r^*s^*)$, and so $$ L((r|s)^*) \subseteq L((r^*s^*)^*). $$

$\endgroup$
0
3
$\begingroup$

Your mistake is in the step $$ L(r|s)^i = L(r)^i \cup L(s)^i. $$ Consider for example $r=a$ and $s=b$. Then $L(r|s)^i$ consists of all words (over $\{a,b\}$) of length $i$, whereas the righthand side is $\{a^i,b^i\}$.

$\endgroup$
3
  • $\begingroup$ You're right, but this doesn't answer my question. $\endgroup$
    – Jay Jay
    Apr 1, 2017 at 7:01
  • $\begingroup$ Well, I'm not planning to do your homework. Perhaps someone else will. $\endgroup$ Apr 1, 2017 at 7:24
  • $\begingroup$ Your assumption is wrong, this is not homework. I, and some friends of mine, have been fighting this identity for a while without success and that's why I decided to post it in here, hoping to have some help. $\endgroup$
    – Jay Jay
    Apr 1, 2017 at 7:43

Your Answer

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

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