-2
$\begingroup$

$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?

$\endgroup$
  • 2
    $\begingroup$ $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. $\endgroup$ – David Richerby Aug 6 '16 at 18:52
0
$\begingroup$

Here are some hints. Start with

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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