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
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