# Proving that $S^* = (S^*)^*$

I am going through some past exam paper questions on regular languages for some revision, and I am having a bit of trouble with converting general ideas into formal mathematical proofs.

The question is:

Given regular expression $$S$$, prove formally that $$S^* = (S^*)^*$$.

My problem is expressing this in a formal proof. Here is what I have worked through so far (it is a bit all over the place and just a collection of ways to express the problem mostly)

$$S^* = (S^*)^*$$

this implies:

$$S^* \subseteq (S^*)^*$$ and $$S^* \supseteq (S^*)^*$$

if we assume that there exists $$w_k$$ such that $$w_k \in S^*$$

then the base case for the proof is:

$$k = 0$$ $$(w_k = \epsilon)$$ (empty word, always in $$S^*$$ and $$(S^*)^*$$ by definition)

$$k = 1$$ $$(w_k \in S^*)$$

and that's kind of where my ability to reason ends.

I think the rest of it will be something like:

$$w_{k+1} = w_kx$$

ie. $$w_k$$ concatenated with $$x$$ where $$x \in S^*$$

but how can I show that $$w_{k+1} \in (S^*)^*$$?

Any help to push me in the right direction would be greatly appreciated.

As you observed, to show $$S^*=(S^*)^*$$ it will suffice to show $$S^*\subseteq(S^*)^*$$ and $$(S^*)^*\subseteq S^*$$. Here's a sketch of a proof of both containments.
For a language $$A$$, define $$A^*=\{x_1x_2\dots x_n\mid n\ge 0\text{ and each }x_i\in A\}$$. Then (with $$n=1$$) it's clear that for all $$x\in A$$ we'll have $$x\in A^*$$, establishing that $$S^*\subseteq(S^*)^*$$.
To show containment in the opposite direction, let $$x\in (S^*)^*$$, then by definition we'll have $$x=y_1y_2\dots y_n$$ where $$y_i\in S^*$$ for all $$1 \le i\le n$$. Then, again by definition, we'll have $$y_i=z_{i1}z_{i2}\dots z_{in_i}$$ where $$z_{ij}\in S$$ for all suitable $$i$$. We'll then have $$x=(z_{11}z_{12}\dots z_{1n_1})(z_{21}z_{22}\dots z_{2n_2})\dots(z_{n1}z_{n2}\dots z_{nn_n})$$ where each $$z_{ij}\in S$$. Applying the definition of star one more time we see that $$x\in S^*$$, establishing that $$(S^*)^*\subseteq S^*$$ and hence the desired equality.
Let L be the set of strings derived from S. Prove that both expressions produce exactly the strings $$L_1 L_2 ... L_k$$ for k >= 0 where each $$L_j$$ is in L, and no others.