HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

How to show that L*=(L*)*?

Submitted by: @import:stackexchange-cs··
0
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^+)^$

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.

Context

StackExchange Computer Science Q#9253, answer score: 12

Revisions (0)

No revisions yet.