Regular expression $(A^*B^*)^* = (A+B)^*$ proof

9.4k Views Asked by At

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...

2

There are 2 best solutions below

0
On

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

4
On

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?