Siguiente: Propiedades de cerradura
Un nivel arriba: Autómatas finitos y expresiones
Anterior: Autómatas bidireccionales
Sean
y
dos autómatas finitos. Su semiautómata producto se define sobre el producto cartesiano como sigue:
- estados:
-
,
- estado inicial:
-
q01=(q01,q02),
- transiciones:
-
(se tiene un semiautómata porque aún no hay estados finales). Denotemos por
a este semiautómata.
Es evidente que
Así pues, si definimos como conjunto de estados finales al conjunto
entonces una palabra
será reconocida por el producto si y sólo si lo es por alguno de los autómatas
o
,
es decir, en este caso,
Ahora, si definimos como conjunto de estados finales al conjunto
entonces una palabra
será reconocida por el producto si y sólo si lo es por ambos autómatas
o
,
es decir, en este caso,
Naturalmente, un autómata producto puede reducirse de manera equivalente considerando unicamente su parte accesible, es decir, aplicándole el algoritmo 3.5.
Guillermo Morales-Luna
2000-06-27