Language equivalence proof

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$).

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents