[Math] Concatenation of languages and multiplying strings

computational mathematicscomputer sciencecomputer-arithmetic

I'm having a hard time understanding concatenation of languages. I'm trying to understand how the following can be possible:

|L1L2| $\neq$ |L1| * |L2|

That is, the number of strings in the language L1L2 (the concatenation of L1 and L2) is not equal to
the number of strings in L1 multiplied by the number of strings in L2.

Is this ever true? From every case I've looked at, including the empty string, this doesn't seem to ever be true. Is there some property of infinite strings that I'm missing?

Any help would be appreciated

Best Answer

There are no infinite examples, but there are finite examples when a word of $L_1L_2$ can be made in more than one way by concatenating a word of $L_1$ and a word of $L_2$. For instance, take $L_1=L_2=\{a,aa\}$; then $L_1L_2=\{aa,aaa,aaaa\}$ has only $3$ elements, not $2^2=4$.

Related Question