# kleene-closure

• Nov 6th 2011, 01:11 AM
suslik
kleene-closure
Hello, I stuck with this exercise (Doh)

The kleene-closure of an Language L ist the smallest language, which contines L as subset and the empty word as an element and which is closend under concatenation. I have to profe by solving a-e

a) L $\subseteq$ L*
b) L* $\cdot$ L* $\subseteq$ L*
c) For every L' (over same Alphabet like L) with L $\subseteq$ L' , $\epsilon$ $\in$ L' and L' $\cdot$ L' $\subseteq$ L' obtains L* $\subseteq$ L'.

I think I solved a) by showing

L = {w1 | w1 $\in$ L} L*={w1,.....,wn | n $\in$ N, $w_i$ $\in$ L for all i = 1....n}

=> w1 $\in$ L and w1 $\in$L* => L $\subseteq$L*

b) and c) I stuck and any help will be appreciated (Clapping)

• Nov 6th 2011, 11:19 AM
emakarov
Re: kleene-closure
Quote:

Originally Posted by suslik
b) L* $\cdot$ L* $\subseteq$ L*

Suppose $w\in L^*\cdot L^*$. Then $w=uv$ for some $u, v\in L^*$, i.e., u and v are concatenations of words from L. What can you way about uv?

Quote:

Originally Posted by suslik
c) For every L' (over same Alphabet like L) with L $\subseteq$ L' , $\epsilon$ $\in$ L' and L' $\cdot$ L' $\subseteq$ L' obtains L* $\subseteq$ L'.

The definition of $L^*$ says that it is the smallest language satisfying these properties.
• Nov 6th 2011, 11:37 AM
suslik
Re: kleene-closure
Perhaps that uv is already in L* because every concatenation of L is already in L* ?
• Nov 6th 2011, 12:23 PM
emakarov
Re: kleene-closure
Yes, if u and v are concatenations of words in L, then so is uv, and therefore it is in L*.