Please answer the following question and give me the reasoning.
Are the following statements true or false? If a statement is false, give a counterexample.
- $uv=vu$ for all strings $u ≠ λ$ and $v ≠ λ$ over an alphabet $Σ={A,B}$.
- $|L_1L_2|=|L_1| × |L_2|$ for all languages $L_1$ and $L_2$ over the alphabet $Σ={A,B}$. For example, if $L_1$ has 3 strings and $L_2$ has 4 strings, then the concatenation $L_1L_2$ always has $3 × 4 = 12$ strings.
- Take the words $u:=$"$A$" and $v:=$"$B$". Are the words "$AB"$ and "$BA$" the same? No.
- Well, indeed, we have a canonical map $L_1\times L_2\to L_1L_2$:
$$\langle u,v\rangle\ \mapsto\ uv$$
but this doesn't need to be bijection if $L_1,\ L_2$ can be any subset of words, as in the following example:
Here the string "$AA$" arises twice in $L_1L_2$, and we have $L_1L_2=\{$"$A$", "$AA$", "$AAA$"$\}$ so that $$|L_1L_2|=3\ \ne\ |L_1|\times|L_2|=4\,.$$