viernes, 11 de diciembre de 2009

AUTÓMATAS CONEXOS

Estados accesibles y Autómatas conexos

Definición:

Sea un AFD = (E, Q, f, q0, F),
el estado p es ACCESIBLE desde q si f’(q, x) = p. En otro caso se dice que es INACCESIBLE.
Resultado: Todo estado es accesible desde sí mismo pues f’(p, λ ) = p

Por tanto, un autómata es conexo si todos los estados son accesibles desde el estado inicial. Para convertir un autómata no conexo en conexo hay que eliminar los estados no accesibles.Es importante destacar que un autómata conexo y su no conexo equivalente, reconocen el mismo lenguaje.

CONEXO



NO CONEXO

No hay comentarios:

Publicar un comentario en la entrada