Autómata finito no determinista

Es el autómata finito que tiene transiciones vacías o que por cada símbolo desde un estado de origen se llega a más de un estado destino, es decir, es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado, tal que para un símbolo  del alfabeto, existe más de una transición posible.

La definición formal de AFND se basa en la consideración de que a menudo según los algoritmos de transformación de expresiones y gramáticas regulares a AF terminan obteniéndose autómatas con transiciones múltiples para un mismo símbolo o transiciones vacías. Independientemente que sean indeseables, sobre todo para la implementación material, fundamentalmente mecánica, de los autómatas finitos, son imprescindibles durante la modelación de analizadores lexicográficos de los elementos gramaticales de los lenguajes de programación, llamados tókens, como literales numéricos, identificadores, cadenas de texto, operadores, etc.

1. Q es un conjunto finito de estados.

2. Σ es un conjunto finito de símbolos de entrada.

3. q0, un elemento de Q, es el estado inicial.

4. F, un subconjunto de Q, es el conjunto de estados finales (o de aceptación).

5. δ , la función de transición, es una función que toma como argumentos un estado de Q y un símbolo de

entrada de Σ y devuelve un subconjunto de Q. Observe que la única diferencia entre un AFN y un AFD

se encuentra en el tipo de valor que devuelve δ : un conjunto de estados en el caso de un AFN y un único

estado en el caso de un AFD.