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

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

You can also check what happens if you replace one, two, or three of the stars in the expression with “+”. With some changes the expression stays true.