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^*)^*$
intuitively i can tell that because S* is an infinite set, then concatenating any number of elements from that infinite set, to that same infinite set, still yields an infinite set of the same size; ie. anything that is in $(S^*)^*)$ must also be in $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 would be greatly appreciated..
Let $w\in S^*$. Since $(S^*)^*$ contains all concatenations of any finite number of words from $S^*$, it certainly contains $w$, which is a concatenation of just one word from $S^*$. So $S^*\subseteq(S^*)^*$.
Conversely, let $w\in(S^*)^*$. By definition we have $$w=w_1w_2\cdots w_n$$ for some $n\ge0$, where each $w_j$ is in $S^*$. By definition again, each $w_j$ can be written as $$w_j=w_{j1}w_{j2}\cdots w_{jm_j}$$ for some $m_j\ge0$, where each $w_{jk}$ is in $S$. So $$w=w_{11}\cdots w_{1m_1}w_{21}\cdots w_{2m_2}\cdots w_{n1}\cdots w_{nm_n}\ .$$ This is a concatenation of finitely many words from $S$, so it is in $S^*$. Therefore $(S^*)^*\subseteq S^*$, and this completes the proof.