equivalent regular expr

Question

Given a regular expression $r_1$, is $(r_1^*)^* = (r_1^*)$. I know that this is true but I do not know how to prove it.

Would it be adequate to set $r_1$ to a regular expression such as $(a+b)$ for example? Then showing that all the elements are found in both the RHS and LHS? i.e. $L((r_1^*)^*)$ is a subset of $L(r_1^*)$ and vice versa?

I tried to use an FA to show that they both would be accepted by the same FA but I don't think that is sufficient for a proof. for instance this

FA

Any sort of direction or help would be much appreciated.

Answer 1

The following result holds for any language $L$ (regular or not): $(L^*)^* = L^*$. Actually, a similar result holds for any monoid $M$. Given a subset $S$ of $M$, define $S^*$ as the submonoid generated by $S$, that is, the smallest submonoid of $M$ containing $S$. Equivalently $S^*$ is the smallest subset $N$ of $M$ containing $S$ and $1$ (the identity of $S$) and such that for all $x, y \in N$, $xy \in N$.

I claim that $(S^*)^* = S^*$. Indeed, since $(S^*)^*$ is a monoid containing $S$, it contains the smallest monoid containing $S$, namely $S^*$. Thus $S^* \subseteq (S^*)^*$. To prove the opposite inclusion, let $N = S^*$. Then $N$ contains $S^*$ (by definition) and $1$ and for all $x, y \in N$, $xy \in N$ (since $S^*$ is a monoid). Therefore $N$ contains the smallest monoid with these properties, namely $(S^*)^*$. Thus $S^* = (S^*)^*$.

Answer 2

It is straightforward that $(r_1*)$ is contained in $(r_1*)*$ .

Next, prove that $(r_1*)(r_1*)$ is contained in $(r_1*)$. (Use double induction.)

Finally, prove that $(r_1*)*$ is contained in $(r_1*)$. (Use induction.)