Multiplication of Languages 

*Suppose you have two languages L1 and L2 over the alphabet {a, b}. Give
an example of L1 and L2 such that |L1 · L2| < |L1| · |L2|. For all possible choices of L1, L2, what is the smallest value of |L1| + |L2| such that
|L1 · L2| < |L1| · |L2|? Show why this is true. (Note that · is normal
multiplication when dealing with numbers like sizes of sets.)


Definition of a language: a language is a set of strings. A language is written using an alphabet. L ⊆ Σ*
is a language
Definition of cardinality: |w| = 0 if w = ε
|ax| = 1 + |x| if w = ax where a ∈ Σ and x ∈ Σ*
abc| = 1 + |bc| = 1 + 1 + |c| = 1 + 1 + 1 + |ε| = 1 + 1 + 1 + 0 = 3
I've tried to prove this but am still having trouble understanding this. All the languages I came up with have the same cardinality multiplied together or seperate
 A: If we look at all the combinations $vw$ such that $v\in L_1$ and $w\in L_2$, then there are a total of $|L_1|\cdot |L_2|$ of such combinations, so in order to have $|L_1\cdot L_2|<|L_1|\cdot |L_2|$, we need at least two combinations $vw$ and $v'w'$ such that $vw=v'w'$ but $v\neq v'$ (and thus $w\neq w'$).
So we need to have a combined string that can be build in two different ways using a string from $L_1$ and a string from $L_2$. I leave it to you to find an example.

To find the smallest value of $|L_1|+|L_2|$, we simply try case by case until we find a suitable pair of languages. 


*

*If one of the two languages is empty, then $|L_1\cdot L_2|=0$, because we cannot build any composite strings from an empty language, and $|L_1|\cdot|L_2|=0$, since we multiply by zero.

*If either of the two languages has only a single element, let's say $|L_1|=1$, then we similarly see that $|L_1\cdot L_2|=|L_1|\cdot |L_2|=|L_2|$.

*The smallest value for $|L_1|+|L_2|$ must therefore be larger than or equal to $4$. There is an easy example to be found with both languages containing exactly two elements for which also $|L_1\cdot L_2|<|L_1|\cdot|L_2|=4$. (Hint: we can even find an example with $L_1=L_2$).

