Propriedades da operação de concatenação de palavras

---

A concatenação é o ato de “juntar” duas palavras, uma após a outra, para formar uma nova palavra.

Formalmente, a concatenação é uma operação que combina duas palavras sobre um alfabeto $\Sigma$. Se $x$ e $y$ são palavras em ${\Sigma }^{\ast }$, a concatenação $xy$ é a palavra obtida colocando $y$ imediatamente após $x$.

As propriedades dessa operação são:

1. Elemento Neutro: A palavra vazia, denotada por $ϵ$, satisfaz:

   $$ϵx=xϵ=x$$

   para qualquer palavra $x\in {\Sigma }^{\ast }$.

2. Associatividade: Para quaisquer palavras $x,y,z\in {\Sigma }^{\ast }$, vale:

   $$(xy)z=x(yz)$$

3. Comprimento aditivo: O comprimento da palavra concatenada é a soma dos comprimentos das palavras originais. Se $|x|$ denota o comprimento de $x$, então:

   $$|xy|=|x|+|y|$$

Propriedade 1: elemento neutro

A palavra vazia $ϵ$ é especial porque não adiciona nenhum símbolo ao resultado da concatenação.

Se você junta $ϵ$ com qualquer palavra $x$, o resultado é simplesmente $x$. Isso é análogo ao número 1 na multiplicação ou ao 0 na soma: um elemento que “não interfere” no resultado.

Por exemplo:

• $ϵx=ϵ\cdot ab=ab=x$.
• $xϵ=ab\cdot ϵ=ab=x$.

A palavra vazia “desaparece” na concatenação, deixando $x$ intacto.

Propriedade 2: associatividade

A associatividade significa que a ordem em que concatenamos três ou mais palavras não importa, desde que a sequência dos operandos seja mantida.

Por exemplo, ao concatenar $x$, $y$ e $z$, podemos primeiro juntar $x$ e $y$ e depois adicionar $z$, ou juntar $y$ e $z$ e depois concatenar com $x$ — o resultado é o mesmo.

$$(xy)z=x(yz)$$

Abaixo está alguns exemplos aplicando essa propriedade:

• $(xy)z=(ab\cdot ba)\cdot a=abba\cdot a=abbaa$.
• $x(yz)=ab\cdot (ba\cdot a)=ab\cdot baa=abbaa$.

Observe que ambos os resultados são iguais, confirmando a associatividade.

Propriedade 3: Aditividade do comprimento

O comprimento de uma palavra concatenada é intuitivo: se $x$ tem 2 símbolos e $y$ tem 3, então $xy$ tem 5 símbolos.

Essa propriedade é especialmente útil para analisar o tamanho das palavras geradas e para verificar condições em linguagens, como “palavras de comprimento par”.

Por exemplo, a palavra $xy=01110$ tem comprimento 5, que é ímpar, então ela não pertence a $L$. Mas se concatenarmos $x$ com outra palavra de comprimento par, como $z=00$ ($|z|=2$):

$xz=01\cdot 00=0100$. $|xz|=|x|+|z|=2+2=4$ (par).

Essa nova palavra $0100$ pertence a $L$, pois tem comprimento par.

Referências

---

Aula 2 - Alfabetos palavras e linguagens