I am studying formal language theory and have been asked to prove the following:

$\forall L, L^*=(L^*)^*$

I've started with

$def. L^* = \bigcup_{i \in \mathbb{N}} L_i, L_0=\{{\epsilon}\}, L_1=\{L\}, L_{i+1}=\{uv|u\in L_i, v\in L\}$

$then (L^*)^* = \bigcup_{i \in \mathbb{N}} L_i^*, L_0^*=\{{\epsilon}\}, L_1^*=\{L^*\}, L_{i+1}^*=\{uv|u\in L_i^*, v\in L^*\}$

$L^*L_0^*\in(L^*)^* = L^*\epsilon^* = L^*$ $\therefore L^* \subseteq (L^*)^*$

$L^*L_0^* = L^*, L^*L^*_1 = L^* (def), L^*L_{i+1}^*=L^*_iL^*=L^*L^*$ but the * operator is closed under concatenation, thus, $L^*L^* \in L^* \therefore (L^*)^* \subseteq L^*$

$\therefore L^* = (L^*)^*$

I simply don't have an intuition on whether this attempt at a proof is correct and I would appreciate any insight about it since the subsequent problems are to show $L^+=(L^+)^+$ and then to argue whether $(L^*)^+=(L^+)^*$

  • 1
    $\begingroup$ If it is "axiomatically true", as you state, there is no point in proving it. What axioms are you using? $\endgroup$
    – vonbrand
    Jan 28, 2013 at 16:11
  • $\begingroup$ @vonbrand Sorry, I misread a set of axioms of a specific Kleene algebra presented in Kozen's text book on automata and computability. $\endgroup$
    – Stephen
    Jan 30, 2013 at 15:33

2 Answers 2


It's a big problem if you can't tell whether your proof counts as a proof or not. Perhaps it's better to write the proof "in words". Here is an example.

Since $M \subseteq M^*$ for every language $M$, clearly $L^* \subseteq (L^*)^*$. Now suppose $w \in (L^*)^*$. Then $w = w_1 \ldots w_\ell$ for some $w_1,\ldots,w_\ell \in L^*$. Then for each $i$, $w_i = w_{i,1} \ldots w_{i,\ell_i}$, where $w_{i,j} \in L$. So $w = w_{1,1} \ldots w_{1,\ell_1} \ldots w_{\ell,1} \ldots w_{\ell,\ell_\ell} \in L^*$. This shows that $(L^*)^* \subseteq L^*$, and so $L^* = (L^*)^*$.

This is probably very similar to the proof you give, but your proof is written "in symbols" and so it is somewhat hard to parse.

  • $\begingroup$ Yes, it is a big problem :) I'm blaming it on a lack of proof writing ... which I am certain will be remediated soon enough! :-) $\endgroup$
    – Stephen
    Jan 29, 2013 at 0:52

We should prove that $L^* \subseteq (L^*)^*$ and then $(L^*)^* \subseteq L^*$.

The first case follows from showing that for every set $A$, we have $A \subseteq A^*$, then let $A = L^*$. The second follows from noticing that every $(L^*)^*$ is made of factors of $L^*$ and every word of $L^*$ is made of factors of $L$, therefore every word in $(L^*)^*$ is a word in $L^*$. This proves the theorem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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