snippetModerate
How to show that L*=(L*)*?
Viewed 0 times
showthathow
Problem
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^+)^$
$\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^+)^$
Solution
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.
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.
Context
StackExchange Computer Science Q#9253, answer score: 12
Revisions (0)
No revisions yet.