# Kleene star of L

$L^*$ is the kleene star of L.

say we have a def: $L^*$ = $L^0$ U $L^1$ U $L^2$ U ... U $L^K$

then prove that: $L^*$ = $L$ if and only if $L$ = $L$ o $L$

how do i prove this?

• $L^*$ is completely standard notation, so you don't need to say what it is, or define it. But what's $L\circ L$? And, for the question, what did you try? Where did you get stuck? We're happy to help with conceptual problems but the point of this kind of exercise is for you to learn by doing, not by getting somebody else to do it for you. – David Richerby Aug 6 '16 at 18:52

Lemma. If $L=L\circ L$, then $\epsilon\in L$.

Proof. By contradiction: consider a string $y\in L$ of minimal length and assume to the contrary that $|y|>0$, then show that $y$ cannot be in $L\circ L$, contradicting the assertion $L=L\circ L$.

Now show that $L=L\circ L\Longleftrightarrow L^*=L$:

$(\Rightarrow)$: If $L=L\circ L$, then since $L^*=\{\epsilon\}\cup L \cup (L\circ L)\cup (L\circ L\circ L)\cup\dotsc$ by definition, we can show that $L^*=L$ by observing, first, that all the terms $L\circ L, L\circ L\circ L, \dotsc$ are equal to $L$ and, second, that $\epsilon\in L$ by our lemma, so $L^*=L$.

$(\Leftarrow)$: Now assume $L^*= L$; we'll show $L=L\circ L$

$\quad(L\subseteq L\circ L)$: Since $\epsilon\in L^*$, we know $\epsilon\in L$ (why?), so $L=\{\epsilon\}\circ L\subseteq L\circ L$.

$\quad(L\circ L\subseteq L)$: Trivial. Left to the reader.