Sean
,
dos semiautómatas finitos. Un homomorfismo, escrito formalmente
,
es una función
que cumple con las condiciones siguientes
h ``preserva'' a las transiciones, es decir,
en otras palabras, el siguiente diagrama es conmutativo
y
el estado inicial de
se aplica en el de
,
es decir,
h(q01)=q02.
Si
y
son dos autómatas con semiautómatas adyacentes
y
entonces un homomorfismo
es un homomorfismo
tal que los estados finales de
se aplican en finales de
,
es decir,
.
Si existe un homomorfismo
decimos que
es una imagen homomorfa de
.
Ejemplo. Consideremos el semiautómata
de 35 estados siguiente:
Sea
el semiautómata de 5 estados siguiente:
Sea
la aplicación definida como sigue:
Entonces h es un homomorfismo de semiautómatas.
Si consideramos como estados finales en
a los estados
q2, q3, q6, q15, q16, q18, q21, q23, q25, q33 y en
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
entonces el autómata
subsume al autómata
.
Para esto, hay que ver que toda palabra reconocida en
también ha de ser reconocida en
.
Se tiene las implicaciones siguientes:
qed.
Es evidente que vale la
Observación 2.1
Si el autómata
es una imagen homomorfa del autómata
mediante un homomorfismo
entonces las siguientes tres proposiciones son lógicamente equivalentes a pares:
1.
y
son equivalentes.
2.
.
3.
.
Un homomorfismo
es un isomorfismo si h es inyectivo y suprayactivo. Si existe un isomorfismo de un autómata
a un autómata
,
se dice que ambos son isomorfos, y en tal caso difieren tan solo por la manera en la que se nombra a sus estados.
Siguiente:Monoide de un semiautómataUn nivel arriba:Autómatas finitos Anterior:Conceptos básicosGuillermo Morales-Luna
2000-06-27