[Solved]: How to show that L*=(L*)*?

Problem Detail: 

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

Asked By : Stephen

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9253

 Ask a Question

 Download Related Notes/Documents