Dotemos al diccionario
de un alfabeto
de la operación de concatenación:
que a cada dos palabras
,
le asocia la palabra que se obtiene de pegar, tras los símbolos de la primera palabra, a los símbolos de la segunda. Nos referiremos indistintamente a esta operación como de concatenación o de yuxtaposición.
Se ve inmediatamente que se cumplen las proposiciones siguientes:
Proposición 2.1
La concatenación es asociativa:
Consecuentemente,
con la concatenación, es decir, la estructura
,
es un semigrupo.
Proposición 2.2
La palabra vacía
es una unidad, por ambos lados, para la concatenación:
Por tanto, la estructura
es un monoide.
Proposición 2.3
Las leyes de cancelación se cumplen por ambos lados:
Sin embargo, como un hecho, digamos ``negativo'', se tiene que la concatenación no es conmutativa.
El diccionario sobre un alfabeto, bien que es infinito, es numerable.
Proposición 2.4
Para todo alfabeto ,
su diccionario
es un conjunto numerable.
En efecto, supongamos que
.
A cada palabra de longitud fija, digamos k, la podemos ver como la representación en base m de un único número entero entre 0 y mk-1, inclusive. Esto da una enumeración efectiva de cada bloque de palabras de longitud fija. Colocamos los bloques, ya enumerados, según el orden de k. Esto da una enumeración de .
Más precisamente, definamos
como sigue:
Así, por ejemplo, para el alfabeto
de m=26 caracteres se tiene