Search code examples
regexconcatenationregular-language

For any language L over ∑*, L* L*=L*

Learning this for one of my classes

For every language L over ∑ * , L* L*=L*

Is this true or false?

I feel that it's false since because when you concatenate two languages the size of the elements is larger than either of the languages being concatenated. Am I thinking about this the right way?

Solution

  • No, you are not thinking about this the right way. Your intuitions will lead you astray at first. In this case, just because the formula is larger doesn't mean that the set is larger.

    Let's suppose L = a.

    So, what are the members of L*? Λ, a, aa, aaa, etc.

    What are the members of L*L*, which is equal to a*a*? Λ, a, aa, aaa, etc.

    You can see that in this case they are the same. Can you think of any case where a member of L*L* is not also a member of L*? (Hint: no. why not?)