next up previous contents
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:

\begin{displaymath}\forall \sigma_1,\sigma_2,\sigma_3\in\Sigma^*:\ \ (\sigma_1\sigma_2)\sigma_3=\sigma_1(\sigma_2\sigma_3).\end{displaymath}

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:

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

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:

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

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 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 $\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*}



next up previous contents
Siguiente: Relaciones de orden Un nivel arriba: Monoide de cadenas Anterior: Monoide de cadenas
Guillermo Morales-Luna
2000-06-27