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
0 comments:
Post a Comment
Let us know your responses and feedback