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

$$\sigma\approx_{\mbox{\scriptsize\it SAF}}\tau\ \ \Leftrightar... ...SAF}}(q_0,\sigma) = T_{\mbox{\scriptsize\it SAF}}(q_0,\tau).$$ (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'':

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

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,

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

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}}$.