Siguiente: Indistinguibilidad de estados en Un nivel arriba: Cocientes de autómatas Anterior: Cocientes de autómatas

Congruencias de autómatas

Sea $\mbox{\it SAF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0)$ un semiautómata. Una relación de equivalencia ``$\equiv$'' definida en el conjunto de estados Q se dice ser congruente con la función de transición si

$$\forall p,q\in Q:\ \ p\equiv q\ \ \Rightarrow\ \ \forall e\in... ...nt\/}:\ \mbox{\it tran\/}(p,e)\equiv \mbox{\it tran\/}(q,e),$$ (9)

es decir para cada símbolo, los estados a los que transita el semiautómata desde sendos estados equivalentes son también equivalentes. Si ``$\equiv$'' es una congruencia, entonces el cociente $Q/\equiv$ puede ser dotado de una estructura de semiautómata:

$$\begin{eqnarray*}Q/\equiv &:& \mbox{\rm estados,} \\ \mbox{\it tran\/}':([q],e... ...\rm transici\'on,} \\ {[q_0]} &:& \mbox{\rm estado inicial.} \end{eqnarray*}$$

y éste se dice ser el semiautómata cociente respecto a la congruencia ``$\equiv$'', denotado como $\mbox{\it SAF\/}/\equiv$. Se tiene pues que la proyección $\pi:q\mapsto [q]$ es un homomorfismo de semiautómatas. Más aún, si $\mbox{\it AF\/}=(\mbox{\it SAF\/},F)$ es un autómata finito y $(\equiv)\subset Q^2$ es una congruencia en el semiautómata $\mbox{\it SAF\/}$, en el cociente $(\mbox{\it SAF\/}/\equiv)$ distinguimos como estados finales a las clases de la forma [q] tales que $[q]\cap F\not=\emptyset$, para obtener el autómata cociente $(\mbox{\it AF\/}/\equiv)$. Aquí, la proyección $\pi$ es un homomorfismo de autómatas. Consecuentemente, el cociente $(\mbox{\it AF\/}/\equiv)$ subsume al autómata $\mbox{\it AF\/}$.

Observación 2.3   Los autómatas $\mbox{\it AF\/}$ y $(\mbox{\it AF\/}/\equiv)$ son equivalentes si y sólo si el conjunto de estados finales F es la unión de algunas clases de equivalencia respecto a ``$\equiv$''.

Para presentar unos primeros ejemplos de congruencias, consideremos homomorfismos de semiautómatas o autómatas. A lo largo de la presente sección, toda vez que hablemos de homomorfismos, supondremos que éstos son de hecho epimorfismos, es decir, como funciones, son suprayectivos. Sean pues $\mbox{\it SAF\/}_1=(Q_1,\mbox{\it Ent\/},\mbox{\it tran\/}_1,q_{10})$ y $\mbox{\it SAF\/}_2=(Q_2,\mbox{\it Ent\/},\mbox{\it tran\/}_2,q_{20})$ dos semiautómatas y $h:\mbox{\it SAF\/}_1\rightarrow \mbox{\it SAF\/}_2$ un homomorfismo. Entonces su núcleo, $\mbox{\it n\'uc\/}(h)=\{(p,q)\vert h(p)=h(q)\}$, es una relación de equivalencia que es de hecho una congruencia. Por tanto, se puede definir el cociente $\mbox{\it SAF\/}_1/\mbox{\it n\'uc\/}(h)$, y éste es tal que cada clase de equivalencia corresponde biunívocamente a un elemento en la imagen de h. Así pues, lo expuesto aquí lo enunciamos como el

Teorema 2.1 (de homomorfismo de semiautómatas)   Si $h:\mbox{\it SAF\/}_1\rightarrow \mbox{\it SAF\/}_2$ es un epimorfismo de semiautómatas entonces el cociente $\mbox{\it SAF\/}_1/\mbox{\it n\'uc\/}(h)$ es isomorfo a $\mbox{\it SAF\/}_2$. En símbolos, $\mbox{\it SAF\/}_1/\mbox{\it n\'uc\/}(h)\equiv\mbox{\it SAF\/}_2$.

Para el caso de autómatas, 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 y $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ es un epimorfismo de autómatas, tal que

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

entonces $F_1=\{[q]_{\mbox{\scriptsize\it n\'uc}(h)}\vert q\in F_1\}$ es la unión de algunas clases de equivalencia respecto a $\mbox{\it n\'uc\/}(h)$. Por tanto los autómatas $\mbox{\it AF\/}_1/\mbox{\it n\'uc\/}(h)$ y $\mbox{\it AF\/}_2$ son isomorfos.

Teorema 2.2 (de homomorfismo de autómatas)   Si $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ es un epimorfismo de autómatas tal que F₁ es la unión de clases de equivalencia respecto a $\mbox{\it n\'uc\/}(h)$, entonces el cociente $\mbox{\it AF\/}_1/\mbox{\it n\'uc\/}(h)$ es isomorfo a $\mbox{\it AF\/}_2$. En símbolos, $\mbox{\it AF\/}_1/\mbox{\it n\'uc\/}(h)\equiv\mbox{\it AF\/}_2$.

Así pues, en cada pareja de semiautómatas o autómatas homomorfos que ya hemos visto, tendremos congruencias de semiautómatas o autómatas y correspondientes estructuras cocientes. Los ejemplos de homomorfismos de semiautómatas y de autómatas que ya hemos visto aquí, han de proporcionar ejemplos de congruencias y de autómatas cocientes.



Siguiente: Indistinguibilidad de estados en Un nivel arriba: Cocientes de autómatas Anterior: Cocientes de autómatas