Siguiente: Monoide de un semiautómata Un nivel arriba: Autómatas finitos Anterior: Conceptos básicos

Homomorfismos

Sean $\mbox{\it SAF\/}_1 = \left(Q_1,\mbox{\it Ent\/},\mbox{\it tran\/}_1,q_{01}\right)$, $\mbox{\it SAF\/}_2 = \left(Q_2,\mbox{\it Ent\/},\mbox{\it tran\/}_2,q_{02}\right)$ dos semiautómatas finitos. Un homomorfismo, escrito formalmente $h:\mbox{\it SAF\/}_1\rightarrow \mbox{\it SAF\/}_2$, es una función $h:Q_1\rightarrow Q_2$ que cumple con las condiciones siguientes

• h ``preserva'' a las transiciones, es decir,
  
  $$\forall q_1\in Q_1,e\in\mbox{\it Ent\/}:\ \ h(\mbox{\it tran\/}_1(q_1,e))=\mbox{\it tran\/}_2(h(q_1),e),$$
  
  
  en otras palabras, el siguiente diagrama es conmutativo
  
  $$\begin{array}{rcl} q_1 &\stackrel{h}{\rightarrow}& q_2 \\ ... ...ackrel{h}{\rightarrow}& \mbox{\it tran\/}_2(q_2,e) \end{array}$$
  
  
  y
• el estado inicial de $\mbox{\it SAF\/}_1$ se aplica en el de $\mbox{\it SAF\/}_2$, es decir, h(q₀₁)=q₀₂.

Si $\mbox{\it AF\/}_1=(\mbox{\it SAF\/}_1, F_1)$ y $\mbox{\it AF\/}_2=(\mbox{\it SAF\/}_2, F_2)$ son dos autómatas con semiautómatas adyacentes $\mbox{\it SAF\/}_1$ y $\mbox{\it SAF\/}_2$ entonces un homomorfismo $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ es un homomorfismo $h:\mbox{\it SAF\/}_1\rightarrow \mbox{\it SAF\/}_2$ tal que los estados finales de $\mbox{\it AF\/}_1$ se aplican en finales de $\mbox{\it AF\/}_2$, es decir, $h(F_1)\subset F_2$. Si existe un homomorfismo $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ decimos que $\mbox{\it AF\/}_2$ es una imagen homomorfa de $\mbox{\it AF\/}_1$.


Ejemplo. Consideremos el semiautómata $\mbox{\it SA35\/}$ de 35 estados siguiente:

$$\begin{array}{ccccc} \begin{array}{\vert\vert r\vert cc\vert... ... q_{16} & q_{ 4} \\ \hline\hline \end{array} \end{array}$$

Sea $\mbox{\it SA5\/}$ el semiautómata de 5 estados siguiente:

$$\begin{array}{\vert\vert r\vert cc\vert\vert}\hline\hline \... ... p_0 & p_1 \\ p_4 & p_0 & p_1 \\ \hline\hline \end{array}$$

Sea $h:\mbox{\it SA35\/}\rightarrow \mbox{\it SA5\/}$ la aplicación definida como sigue:

$$\begin{array}{\vert\vert c\vert c\vert c\vert c\vert c\vert\v... ... q_{34} &\mapsto& p_{ 1} \end{array} \\ \hline \end{array}$$

Entonces h es un homomorfismo de semiautómatas. Si consideramos como estados finales en $\mbox{\it SA35\/}$ a los estados q₂, q₃, q₆, q₁₅, q₁₆, q₁₈, q₂₁, q₂₃, q₂₅, q₃₃ y en $\mbox{\it SA5\/}$ consideramos únicamente a p₂ como estado final, se tiene que h es también un homomorfismo de autómatas.

Proposición 2.1   Si existe un homomorfismo $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ entonces el autómata $\mbox{\it AF\/}_2$ subsume al autómata $\mbox{\it AF\/}_2$.

Para esto, hay que ver que toda palabra reconocida en $\mbox{\it AF\/}_1$ también ha de ser reconocida en $\mbox{\it AF\/}_2$. Se tiene las implicaciones siguientes:

$$\begin{array}{rclcl} \sigma\in L(\mbox{\it AF\/}_1) &\Righta... ...\\ &\Rightarrow& \sigma\in L(\mbox{\it AF\/}_2) \end{array}$$

qed.


Es evidente que vale la

Observación 2.1   Si el autómata $\mbox{\it AF\/}_2=(Q_2,\mbox{\it Ent\/},\mbox{\it tran\/}_2,q_{20}, F_2)$ es una imagen homomorfa del autómata $\mbox{\it AF\/}_1=(Q_1,\mbox{\it Ent\/},\mbox{\it tran\/}_1,q_{10}, F_1)$ mediante un homomorfismo $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ entonces las siguientes tres proposiciones son lógicamente equivalentes a pares:

1.

$\mbox{\it AF\/}_1$ y $\mbox{\it AF\/}_2$ son equivalentes.

2.

$\forall q\in Q_1:\ q\in F_1\ \Leftrightarrow\ h(q)\in F_2$.

3.

$h^{-1}\left(F_2\right)=F_1$.

Un homomorfismo $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ es un isomorfismo si h es inyectivo y suprayactivo. Si existe un isomorfismo de un autómata $\mbox{\it AF\/}_1$ a un autómata $\mbox{\it AF\/}_2$, se dice que ambos son isomorfos, y en tal caso difieren tan solo por la manera en la que se nombra a sus estados.
Siguiente: Monoide de un semiautómata Un nivel arriba: Autómatas finitos Anterior: Conceptos básicos