World's most popular travel blog for travel bloggers.

# 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.

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