# Problems while trying to prove that $(r|s)^* = (r^*.s^*)^*$

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.

• What is dot "." in the RHS of this equation? – Andrey Lebedev Apr 1 '17 at 8:23
• @Andremoniy Concatenation. – Yuval Filmus Apr 1 '17 at 8:25

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