next up previous contents
Siguiente: Cocientes de autómatas Un nivel arriba: Autómatas finitos Anterior: Monoide de un semiautómata

Acceso en un semiautómata

Dado un semiautómata $\mbox{\it SAF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0)$, definamos ahora la relación de equivalencia $\approx_{\mbox{\scriptsize\it SAF}}$ en el diccionario $\mbox{\it Ent\/}^*$ haciendo

 \begin{displaymath}\sigma\approx_{\mbox{\scriptsize\it SAF}}\tau\ \ \Leftrightar...
...SAF}}(q_0,\sigma) = T_{\mbox{\scriptsize\it SAF}}(q_0,\tau).
\end{displaymath} (8)

es decir, dos palabras están relacionadas si ambas arriban a un mismo estado cuando se parte desde el inicial. `` $\approx_{\mbox{\scriptsize\it SAF}}$'' es una relación de equivalencia que, aunque no es congruente con la concatenación, sí es ``invariante bajo concatenaciones a la derecha'':

\begin{displaymath}\sigma_1\equiv_{\mbox{\scriptsize\it SAF}}\sigma_2,\tau\in \m...
...w\ \sigma_1\tau\approx_{\mbox{\scriptsize\it SAF}}\sigma_2\tau.\end{displaymath}

De las relaciones (3.2) y (3.4) se tiene que vale la siguiente:

Observación 2.2   La relación `` $\equiv_{\mbox{\scriptsize\it SAF}}$'' es un refinamiento de la relación `` $\approx_{\mbox{\scriptsize\it SAF}}$'', es decir,

\begin{displaymath}\forall\sigma_1,\sigma_2\in \mbox{\it Ent\/}^*:\ \ \sigma_1\e...
...ightarrow\ \sigma_1\approx_{\mbox{\scriptsize\it SAF}}\sigma_2.\end{displaymath}

Ahora, es claro que cada estado accesible del semiautómata SAF determina una clase de equivalencia bajo la relación `` $\approx_{\mbox{\scriptsize\it SAF}}$''. Por tanto, el cociente $\mbox{\it Ent\/}^*/\approx_{\mbox{\scriptsize\it SAF}}$ puede identificarse naturalmente con la parte accesible de SAF, y, consecuentemente, la estructura de semiautómata de este último se traslada de manera directa al cociente $\mbox{\it Ent\/}^*/\approx_{\mbox{\scriptsize\it SAF}}$.

Guillermo Morales-Luna
2000-06-27