next up previous contents
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 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{displaymath}\begin{array}{ccccc}
\begin{array}{\vert\vert r\vert cc\vert...
... q_{16} & q_{ 4} \\
\hline\hline
\end{array}
\end{array} \end{displaymath}

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

\begin{displaymath}\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}\end{displaymath}

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

\begin{displaymath}\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} \end{displaymath}

Entonces h es un homomorfismo de semiautómatas. Si consideramos como estados finales en $\mbox{\it SA35\/}$ a los estados q2, q3, q6, q15, q16, q18, q21, q23, q25, q33 y en $\mbox{\it SA5\/}$ consideramos únicamente a p2 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{displaymath}\begin{array}{rclcl}
\sigma\in L(\mbox{\it AF\/}_1) &\Righta...
...\\
&\Rightarrow& \sigma\in L(\mbox{\it AF\/}_2)
\end{array}\end{displaymath}

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.
next up previous contents
Siguiente: Monoide de un semiautómata Un nivel arriba: Autómatas finitos Anterior: Conceptos básicos
Guillermo Morales-Luna
2000-06-27