Are these statements concerning formal languages true or false, and why?

902 Views Asked by At

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.

  1. $uv=vu$ for all strings $u ≠ λ$ and $v ≠ λ$ over an alphabet $Σ={A,B}$.
  2. $|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.
1

There are 1 best solutions below

2
On

  1. Take the words $u:=$"$A$" and $v:=$"$B$". Are the words "$AB"$ and "$BA$" the same? No.
  2. 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:

    $L_1:=\{$"$A$","$AA$"$\}$
    $L_2:=\{$"", "$A$"$\}$.

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\,.$$