# How to show that L*=(L*)*?

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^+)^*$

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

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