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

Homomorfismos

Sean (S₁,*₁,u₁) y (S₂,*₂,u₂) dos monoides con operaciones respectivas *₁ y *₂ y unidades u₁ y u₂. 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,+)$:

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

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

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

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

• $\sigma_1$ es un prefijo de $\sigma_2$ si $\exists \sigma\in\Sigma^*:\ \sigma_2=\sigma_1\sigma.$
• $\sigma_1$ es un sufijo de $\sigma_2$ si $\exists \sigma\in\Sigma^*:\ \sigma_2=\sigma\sigma_1.$
• $\sigma_1$ es un enfijo de $\sigma_2$ si $\exists \sigma',\sigma''\in\Sigma^+:\ \sigma_2=\sigma'\sigma_1\sigma''.$

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,

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

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

$$(\sigma_1,\sigma_2)\mapsto\mbox{\it suf\/}_n(\sigma_1\sigma_2).$$

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 f_s(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 (S₁,*₁,u₁) y (S₂,*₂,u₂) 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 S₂ 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

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

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{array}{c} dabale\, arroz\, a\, la\, zorra\, el\, abad... ...mota \\ a\, man\, a\, plan\, a\, canal\, panama \end{array}$$

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