Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
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! :-) –  Stephen Jan 29 '13 at 0:52
add comment

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

The first case follows from showing that for every set $A$, we have $A \subset 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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