Dado un semiautómata
,
definamos ahora la relación de equivalencia
en el diccionario
haciendo
(8)
es decir, dos palabras están relacionadas si ambas arriban a un mismo estado cuando se parte desde el inicial.
``
'' es una relación de equivalencia que, aunque no es congruente con la concatenación, sí es ``invariante bajo concatenaciones a la derecha'':
De las relaciones (3.2) y (3.4) se tiene que vale la siguiente:
Observación 2.2
La relación ``
'' es un refinamiento de la relación ``
'', es decir,
Ahora, es claro que cada estado accesible del semiautómata SAF determina una clase de equivalencia bajo la relación ``
''. Por tanto, el cociente
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
.
Guillermo Morales-Luna
2000-06-27