**Problem Detail:**

Can anyone explain to me how the following is true for any language?

$$L^+ = LL^* = L^*L$$

I'm confused because $L^*$ is the set of all words including the empty string, while $L^+$ is the set of all words excluding the empty string. I don't understand how concatenating $L^*$ with $L$ makes it equal to $L^+$. What happens to the empty string? Thank you.

###### Asked By : AmazingBergkamp

###### Answered By : David Richerby

In general, $L^*$ is not the set of all words. $L^*$ is the set of all words that can be made by taking any number of words from $L$, including zero, and sticking them together (concatenating them). $L^+$ is the set of all words that can be made by sticking together any *positive* number of words from $L$ (not including zero).

So, if you stick together one or more words ($L^+$), that's equivalent to taking one and then adding zero or more ($LL^*$), and it's equivalent to taking zero or more and adding another one ($L^*L$).

Question Source : http://cs.stackexchange.com/questions/35388

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback