# induction proof for kleene star

i posted this on mathematics stack exchange here before i realised this one existed.

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^*$.

(EDIT: thanks to David Richerby for pointing out this is wrong)

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

• Your paragraph beginning "Intuitively, I can tell" is incorrect. Two infinite sets having the same cardinality in no way means that they are the same set, even if one is a subset of the other: consider the natural numbers versus the odd natural numbers, for example. You also seem to be working backwards: you start by assuming that $S^*=(S^*)^*$ but that's the very thing you're trying to prove! – David Richerby Apr 28 '14 at 12:52
• Please don't crosspost on different SE sites simultaneously! Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration or repost. It may be prudent to include links in either direction and explain why the particular perspective of the other site seems useful. – Raphael Apr 29 '14 at 10:09
• okay, i am sorry i didnt realise that was the policy, i posted on the mathematics SE but then realised it was probably more relevant to this site, i won't in future though. – guskenny83 May 2 '14 at 8:03

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=(x_{11}x_{12}\dots x_{1n_1})(x_{21}x_{22}\dots x_{2n_2})\dots(x_{n1}x_{n2}\dots x_{nn_n})$$ where each $x_{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.