Suponha que A e B sejam subconjuntos finitos de V^{*}, em que V é um alfabeto. En necessariamente verdade que |A B| =|B A| ?

Passo 1

Resumimos o problema: sejam subconjuntos finitos A\subset V^* e B\subset V^* de um alfabeto V. Definimos
AB = \{\,x y \mid x\in A,\;y\in B\}
e
BA = \{\,y x \mid y\in B,\;x\in A\}.
A pergunta é se necessariamente \lvert AB\rvert = \lvert BA\rvert.

Passo 2

Em geral a concatenação satisfaz
\lvert AB\rvert = \lvert A\rvert\,\lvert B\rvert - c_{AB}, \quad \lvert BA\rvert = \lvert A\rvert\,\lvert B\rvert - c_{BA},
onde c_{AB} e c_{BA} são os números de colisões (pares distintos que geram a mesma palavra). Nada garante que c_{AB}=c_{BA}.

Passo 3

Para dar um contra-exemplo escolha V=\{a,b\},
A = \{a,\;ab\}, \quad B = \{\varepsilon,\;b\},
onde \varepsilon é a palavra vazia.

Passo 4

Calculamos
AB=\{\,a\cdot\varepsilon,\;a\cdot b,\;ab\cdot\varepsilon,\;ab\cdot b\} =\{\,a,\;ab,\;ab,\;abb\} =\{\,a,\;ab,\;abb\},
logo \lvert AB\rvert=3.

Passo 5

Calculamos
BA=\{\varepsilon\cdot a,\;\varepsilon\cdot ab,\;b\cdot a,\;b\cdot ab\} =\{\,a,\;ab,\;ba,\;bab\},
logo \lvert BA\rvert=4.

Passo 6

Vemos que
\lvert AB\rvert = 3 \neq 4 = \lvert BA\rvert,
portanto não é sempre verdade que \lvert AB\rvert = \lvert BA\rvert.

Resposta

Não, não é necessariamente verdade. Por exemplo, com A=\{a,ab\} e B=\{\varepsilon,b\} obtemos \lvert AB\rvert=3\neq4=\lvert BA\rvert.

Exercícios de Livros Relacionados