3
$\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$
  • $\begingroup$ What is dot "." in the RHS of this equation? $\endgroup$ – Andrey Lebedev Apr 1 '17 at 8:23
  • $\begingroup$ @Andremoniy Concatenation. $\endgroup$ – Yuval Filmus Apr 1 '17 at 8:25
5
$\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$
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$
  • $\begingroup$ You're right, but this doesn't answer my question. $\endgroup$ – Jay Jay Apr 1 '17 at 7:01
  • $\begingroup$ Well, I'm not planning to do your homework. Perhaps someone else will. $\endgroup$ – Yuval Filmus Apr 1 '17 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 '17 at 7:43

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.