Prove $(L^*)^*=L^*$

84 Views Asked by At

https://i.stack.imgur.com/XJqT4.png

How would I do this? I have tried to think of a solution but nothing comes to my mind.

1

There are 1 best solutions below

0
On

Obviously $L^*\subseteq (L^*)^*$. (Each symbol is a word of length 1).

Conversely take any word $w\in (L^*)^*$. From its definition, it's a concatenation $w=u_1\cdots u_n$ , where each $u_i\in L^*$. From the definition of $L^*$ we have $u_i=v_{(i,1)}\cdots v_{(i,k_i)}$ where all $v_{(i,j)}\in L$. So we can write $$w=(v_{(1,1)}\cdots v_{(1,k_1)})\cdots (v_{(n,1)}\cdots v_{(n, k_n)})$$ and $w\in L^*$ as it's a concatenation of symbols in $L$.