6
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If it is "axiomatically true", as you state, there is no point in proving it. What axioms are you using? $\endgroup$ Commented 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$ Commented Jan 30, 2013 at 15:33

2 Answers 2

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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$ Commented Jan 29, 2013 at 0:52
10
$\begingroup$

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.