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.