definición autómata finito no determinista AFN

  definición autómata finito no determinista AFN

 Determinista: si el autómata no puede estar en más de un estado al mismo tiempo. No determinista: si el autómata puede estar en varios estados al mismo tiempo.

• Cuando una maquina esta en un estado concreto y se lee el siguiente símbolo de entrada, sabemos cual será el siguiente estado porque esta determinado, a esto llamamos cómputo determinista. En cambio en una maquina no determinista, puede haber varias opciones para el siguiente estado. • El no determinismo es una generalización del determinismo, tanto que cada autómata finito determinista es automáticamente un autómata finito no determinista (AFN). • La diferencia entre un AFD y un AFN: 1. Cada estado de un AFD siempre tiene exactamente una flecha de transición para cada símbolo en el alfabeto, en el AFN no sucede así pues puede tener mas de una dirección con el mismo símbolo. En un AFN un estado puede tener cero, una, o muchas flechas para cada símbolo del alfabeto. 2. Segundo, en el AFD, las etiquetas de las flechas de transición son símbolos del alfabeto. En el AFN puede tener flechas etiquetadas con miembros del alfabeto o ε. • En general un AFN puede tener flechas etiquetadas con miembros del alfabeto o ε. Además, cero, uno, o varias flechas pueden salir de cada estado con la etiqueta ε.