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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.