Operaciones con palabras

Concatenación

Sean dos palabras x e y Є W(∑), donde |x|=i, |y|=j y además x=x1 x2...xi e y=y1y2...yj .

La concatenación es otra palabra z, también perteneciente al universo del discurso, que se obtiene añadiendo las letras de y a continuación de las letras de x, es decir z=xy=x.y=x1x2...xiy 1y2...yj.

Se representa como xy o x.y.

Tiene las siguientes propiedades:

1. Es una operación cerrada en el conjunto de palabras de ∑*, es decir, que si x e y pertenecen a ∑*, la concatenación de ambas también pertenece al lenguaje universal
2. Asociativa: x(yz) = (xy)
3. Tiene elemento neutro: la palabra vacía λ. λx=xλ=x
4. No tiene la propiedad conmutativa: xy <> y
5. Cancelación por la izquierda y derecha: a, b, c Є ∑* se cumple que ab = ac b = c y ac = bc a = b respectivamente.

Por cumplir las propiedades 1 y 2 la concatenación de las palabras de un alfabeto es un semigrupo y si además cumple la propiedad 3 es un monoide.

Por otro lado, podemos definir los siguientes conceptos asociados:

Cabeza: sea z=xy (la concatenación de x e y), x es cabeza de z y, además, es cabeza propia si y no es la palabra vacía.

Cola: sea z=xy (la concatenación de x e y), x es cola de z y, además, es cola propia de z si x no es la palabra vacía.

Longitud: esta función tiene respecto a la concatenación propiedades semejantes a la del logaritmo respecto al producto: xy=x+y

Monoide Libre

Sea un alfabeto ∑ y la operación de concatenación:

- Consideramos cada una de las letras del alfabeto palabras de longitud 1 pertenecientes a  W(∑)

- Aplicando a estas palabras la operación concatenación se puede formar cualquier palabra de W (∑) excepto la palabra vacía (λ), es decir   W(∑)–λ.

- Entonces el alfabeto ∑ es un conjunto de generadores de universos del discurso menos λ. El alfabeto junto con la concatenación forma un semigrupo.

- Si se añade λ, entonces se obtiene W(∑) que es el monoide libre generado por ∑.

* Todo monoide libre cumple la ley de cancelación izquierda y derecha:

Para todo x, y, z Є W(∑) Si se cumple xy = xz -> y=z

Para todo x, y, z Є W(∑) Si se cumple xy =zy ->  x=z

Potencia

La potencia de una palabra x Є ∑* es la concatenación de la misma i veces. Es la reducción de la concatenación para la misma palabra.

Tiene las siguientes propiedades:

1. Asociativa
2. x1=x
3. x0=λ
4. xixj=xi+j (i,j ≥ 0)
5. La función longitud es semejante al logaritmo de la potencia: xi=i|x|

Reflexión (o inversión)

Sea x=x1x2…xi Є ∑*, la palabra refleja representada como xR o x-1 es x-1=xi…x2x1 , es decir, por los mismos símbolos en orden inverso, y su longitud es la misma que x.

La función longitud es invariante en la reflexión de palabras

|x|=|x-1|