Regular expression $(A^*B^*)^* = (A+B)^*$ proof The question is as follow: Suppose $A,B$ are regular expressions such that $R_1 = (A^* B^*)^*$ and $R_2 = (A + B)^*$: prove $L(R_1) = L(R_2)$
What I tried to do was: Let $w$ be a string such that $w ∈ x.y$ for strings $x$ and $y$ such that $x \in L(A^*)^*$ and $y \in (B^*)^* = x \in L(A^*).y \in L(B^*)$
But this is as far as I could get and not sure if I'm on the right path or what the next step should be...
 A: I will give you an intuitive proof by induction on the length of the word. We will prove a stronger statement: 

Every $w$ in $L(R_1)$ and $L(R_2)$ is of the form $w=w_1...w_n$ where each word $w_i$ is in $L(A)$ or $L(B)$ or $w$ is the empty string. 

It is definitely true for the base case $|w| = 0$, since it is easy to see that the empty word is in both $L(R_1)$ and $L(R_2)$. Therefore assume it is true for $|w| = 1,...,n$. Suppose that $|w|$ has length $n+1$. By Lemma 1 (below) we see that of the following 


*

*$w = w'a$ for some $a \in L(A)$,

*$w = w'b $ for some $b \in L(B)$, 

*or $w \notin R_1,R_2$
must be true. If the first or second case occurs then the induction hypothesis implies that $w$ is of the form $w=w_1...w_k$ where each word $w_i$ is in $L(A)$ or $L(B)$ (by modifying the argument in Lemma 1). If the third case is true then $w \notin R_1,R_2$ as is needed. 
Lemma 1 One of the three cases above must be true and case 3 is mutually exclusive with the other two cases
(Proof): The reduction to the 3 cases can be rigorously proven by induction on the exponent that witnesses the statement $ x \in L(X^*)  \iff (\exists n \in \mathbb{N}) \ x \in L(X)^n$; i.e. either $x = \emptyset_{\textrm{word}} $ or $x \in L(X)$ or $x \in L(X)\times L(X)$ or $x \in L(X)\times L(X)\times L(X)$ ... 
Setting $X = A+B$ we see that this statement is immediately true and setting $X = A^* B^*$ requires a second similar induction for the two possible cases $x \in A^*$ or $x \in B^*$. Essentially this proof is turtles all the way down. QED
A: To show that $L(R_2)\subseteq L(R_1)$ you should note that $L(A)\subseteq L(A^*)\subseteq L(A^* B^*)$, analogously $L(B)\subseteq L(A^* B^*)$, so $L(A+B)\subseteq L(A^* B^*)$ ah hence $L((A+B)^*)\subseteq L((A^* B^*)^*)$.
For the converse, note that $L(A)\subseteq L(A+B)\subseteq L((A+B)^*)$ and (being the latter concatenation-closed) $L(A^*)\subseteq L(((A+B)^*)^*)=L((A+B)^*)$ analogously $L(B^*)\subseteq L((A+B)^*)$, so, again for concatenation closedness $L(A^*B^*)\subseteq L((A+B)^*)$ and you finally have (for the same reason) $L((A^*B^*)^*)\subseteq L((A+B)^*)$
A: Any word $w \in L((A + B)^*)$ is of the form $w_1 w_2 \ldots w_n$ where each $w_i \in L(A) \cup L(B)$. If $w_i \in L(A)$, then $w_i = w_i \epsilon \in L(A^* B^*)$, and similarly if $w_i \in L(B)$, then $w_i = \epsilon w_i \in L(A^* B^*)$. Hence $w \in L((A^* B^*)^*)$, and so we have $ L((A + B)^*) \subseteq L((A^* B^*)^*)$. Can you make a similar style of argument for the opposite inclusion?
