Siguiente: Relaciones de orden Un nivel arriba: Monoide de cadenas Anterior: Monoide de cadenas

La operación de concatenación

Dotemos al diccionario $\Sigma^*$ de un alfabeto $\Sigma$ de la operación de concatenación:

$$\begin{eqnarray*}\cdot:\Sigma^*\times\Sigma^* &\rightarrow& \Sigma^* \\ (\sigma_1,\sigma_2) &\mapsto& \sigma_1\cdot\sigma_2 \end{eqnarray*}$$

que a cada dos palabras $\sigma_1=s_{10}\cdots s_{1,l_1-1}$, $\sigma_2=s_{20}\cdots s_{2,l_2-1}$ 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:

$$\forall \sigma_1,\sigma_2,\sigma_3\in\Sigma^*:\ \ (\sigma_1\sigma_2)\sigma_3=\sigma_1(\sigma_2\sigma_3).$$

Consecuentemente, $\Sigma^*$ con la concatenación, es decir, la estructura $(\Sigma^*,\cdot)$, es un semigrupo.

Proposición 2.2   La palabra vacía $\mbox{\it nil\/}$ es una unidad, por ambos lados, para la concatenación:

$$\forall \sigma\in\Sigma^*:\ \ \mbox{\it nil\/}\cdot \sigma=\sigma=\sigma\cdot\mbox{\it nil\/}.$$

Por tanto, la estructura $(\Sigma^*,\cdot,\mbox{\it nil\/})$ es un monoide.

Proposición 2.3   Las leyes de cancelación se cumplen por ambos lados:

$$\forall \sigma_1,\sigma_2,\sigma_3\in\Sigma^*:\ \ \begin{arra... ...=\sigma_3\sigma_1 &\Rightarrow& \sigma_2=\sigma_3 \end{array}$$

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 $\Sigma$, su diccionario $\Sigma^*$ es un conjunto numerable.

En efecto, supongamos que $\Sigma=\{s_0,\ldots,s_{m-1}\}$. 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 m^k-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 $\Sigma^*$. Más precisamente, definamos $c:\Sigma^*\rightarrow I\!\!N$ como sigue:

$$\begin{eqnarray*}c(\mbox{\it nil\/})&=&0 \\ c(s_{n_1}s_{n_2}\cdots s_{n_k}) &=& \frac{m^k-1}{m-1}+\sum_{j=1}^k n_j m^{k-j} \end{eqnarray*}$$

Así, por ejemplo, para el alfabeto $\mbox{\it Latino\/}$ de m=26 caracteres se tiene

$$\begin{eqnarray*}c(\mbox{\it zapatista\/}) &=& \frac{26^9-1}{26-1}+25\cdot 26^8+... ... &=& 135737591974375 + 5225319188206 \\ &=& 140962911162581 \end{eqnarray*}$$

$$\begin{eqnarray*}c(\mbox{\it mexico\/}) &=& \frac{26^6-1}{26-1}+12\cdot 26^5+4\c... ...ot 26^1+14\cdot 26^0 \\ &=& 7722894375 +144814138 =7867708513 \end{eqnarray*}$$

Siguiente: Relaciones de orden Un nivel arriba: Monoide de cadenas Anterior: Monoide de cadenas