next up previous contents
Siguiente: Relaciones de equivalencia congruentes Un nivel arriba: Monoide de cadenas Anterior: Orden lexicográfico

Homomorfismos

Sean (S1,*1,u1) y (S2,*2,u2) dos monoides con operaciones respectivas *1 y *2 y unidades u1 y u2. Una función $h:S_1\rightarrow S_2$ es un homomorfismo si

\begin{eqnarray*}\forall x,y\in S_1:\ h(x*_1y) &=& h(x)*_2h(y) \\
h(u_1) &=& u_2
\end{eqnarray*}


En otras palabras, un homomorfismo es una correspondencia entre monoides que preserva las operaciones.

Observación 2.1   El tomar longitudes da un homomorfismo $(\Sigma^*,\cdot)\rightarrow(I\!\!N,+)$:

\begin{displaymath}\forall \sigma_1,\sigma_2\in\Sigma^*:\ \ \mbox{\it long\/}(\s...
...gma_2)=\mbox{\it long\/}(\sigma_1)+\mbox{\it long\/}(\sigma_2).\end{displaymath}

En efecto, sea $(I\!\!N,+,0)$ el monoide que consta de los números naturales con la suma como operación y el 0 como unidad. Sea $\Sigma$ un alfabeto. Ya que $\forall \sigma_1,\sigma_2\in\Sigma^*: \mbox{\it long\/}(\sigma_1\sigma_2)=\mbox{\it long\/}(\sigma_1)+\mbox{\it long\/}(\sigma_2),$ y además $\mbox{\it long\/}(\mbox{\it nil\/})=0$ tenemos que $\mbox{\it long\/}:(\Sigma^*,\cdot,\mbox{\it nil\/})\rightarrow(I\!\!N,+,0)$ es un homomorfismo.

Ejemplos de homomorfismos. 1. Sea $(Z\!\!\!Z_2,+,0)$ el monoide sobre el conjunto $Z\!\!\!Z_2=\{0,1\}$ con la operación suma ''módulo 2'', o, en otras palabras, el complemento de la disyunción exclusiva, XOR. Sea $\Sigma$ un alfabeto y $\mbox{\it par\/}:(\Sigma^*,\cdot,\mbox{\it nil\/})\rightarrow(Z\!\!\!Z_2,+,0)$ la función definida como

\begin{displaymath}\mbox{\it par\/}:\sigma\mapsto\left\{\begin{array}{ll}
0 &\m...
...si $\mbox{\it long\/}(\sigma)$ es impar. }
\end{array}\right.\end{displaymath}

$\mbox{\it par\/}$ es, en efecto, un homomorfismo.

2. Sea $\Sigma$ un alfabeto y sea $f:\Sigma\rightarrow\Sigma^*$ cualquier función. Extendemos f a una función $f^*:\Sigma^*\rightarrow\Sigma^*$ haciendo

\begin{eqnarray*}f^*(\mbox{\it nil\/}) &=& \mbox{\it nil\/}\\
\forall \sigma\in\Sigma^*,s\in\Sigma:\ \ f^*(\sigma s) &=& f^*(\sigma)f(s)
\end{eqnarray*}


f* es un homomorfismo y es, propiamente, una sustitución de símbolos: en cada palabra, cada símbolo s se sustituye por la partícula f(s). El homomorfismo f* se dice libre de $\mbox{\it nil\/}$ si para ningún $s\in \Sigma$ se tiene $f(s)=\mbox{\it nil\/}$.

3. Sea $\Sigma$ un alfabeto. Dadas dos palabras $\sigma_1,\sigma_2\in\Sigma^*$ diremos que Sea n>0. Consideremos la operación $\mbox{\it suf\/}_n:\Sigma^*\rightarrow\Sigma^{\leq n}$ que actúa sobre cualquier palabra suprimiendo, si fuera necesario, un prefijo para quedarse únicamente con el sufijo de longitud n. Más precisamente,

\begin{displaymath}\mbox{\it suf\/}_n:s_{i_1}s_{i_2}\ldots s_{i_k}\mapsto s_{i_{k-n+1}}\ldots s_{i_k}.\end{displaymath}

$\Sigma^{\leq n}$ tiene una estructura de monoide con la operación de concatenación, seguida de $\mbox{\it suf\/}_n$,

\begin{displaymath}(\sigma_1,\sigma_2)\mapsto\mbox{\it suf\/}_n(\sigma_1\sigma_2).\end{displaymath}

Bajo esta transformación que es, en efecto, un homomorfismo, todas las palabras de longitud a lo sumo n permanecen fijas.

Sea $(S,\cdot,u)$ un monoide cualquiera. Consideremos el monoide aditivo sobre el conjunto de números naturales con la suma usual, $(I\!\!N,+,0)$. Entonces se tiene que para todo $s\in S$ existe un único homomorfismo $f_s:I\!\!N\rightarrow S$ tal que fs(1)=s. La imagen de tal homomorfismo es el submonoide $\left(s^n\right)_{n\geq 0}$ y se dice ser el generado por el elemento $s\in S$.


Un antihomomorfismo entre dos monoides (S1,*1,u1) y (S2,*2,u2) es una función $h:S_1\rightarrow S_2$ tal que

\begin{eqnarray*}\forall x,y\in S_1:\ h(x*_1y) &=& h(y)*_2h(x) \\
h(u_1) &=& u_2
\end{eqnarray*}


es decir, es una operación que en el contradominio ''conmuta'' a la operación.

Ejemplos. 1. Si S2 es conmutativo, entonces cualquier homomorfismo es también un antihomomorfismo.

2. Sea $\Sigma$ un alfabeto y sea $\mbox{\it reverso\/}:\Sigma^*\rightarrow\Sigma^{*}$ la función que intercambia de derecha a izquierda los símbolos que conforman una palabra. Inductivamente, se tiene

\begin{eqnarray*}\mbox{\it reverso\/}(\mbox{\it nil\/}) &=& \mbox{\it nil\/}\\ 
...
...ox{\it reverso\/}(\sigma s) &=& s\,\mbox{\it reverso\/}(\sigma)
\end{eqnarray*}


Se ve fácilmente que

\begin{displaymath}\forall \sigma_1,\sigma_2\in\Sigma^*:\ \mbox{\it reverso\/}(\...
...2)=\mbox{\it reverso\/}(\sigma_2)\mbox{\it reverso\/}(\sigma_1)\end{displaymath}

y consecuentemente esta función es un antihomomorfismo. Las palabras fijas bajo este operador son palíndromas. Como meros ejemplos, se tiene a los siguientes:

\begin{displaymath}\begin{array}{c}
dabale\, arroz\, a\, la\, zorra\, el\, abad...
...mota \\
a\, man\, a\, plan\, a\, canal\, panama
\end{array}\end{displaymath}


next up previous contents
Siguiente: Relaciones de equivalencia congruentes Un nivel arriba: Monoide de cadenas Anterior: Orden lexicográfico
Guillermo Morales-Luna
2000-06-27