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

Question

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.

Answer 1

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

Answer 2

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