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.

Los AFND sondefiniciones no tan deseables dentro de los lenguajes regulares porquedificultan su implementación tanto mecánica como informática; aunque en la mayoría de las transformaciones a lo interno de los LR (expresiones regulares a AF, gramáticas regulares a AF) conducen a AFND. Los AFND, por tanto, son imprescindibles en el análisis lexicográfico y el diseño de los lenguajes de programación.

DEFINICIÓN: Sea un autómata finito definido por la quíntupla  A=(Q,Σ,q0 ,δ,F) donde:

Q: es el conjunto finito de estados

Σ: es un alfabeto finito

q0 ∈ Q: es el estado inicial

F⊆Q: es un conjunto de estados finales o de aceptación

δ:Qx(∑∪{ε})→ P(Q): cuando contiene transiciones vacías

δ:Qx∑→ P(Q) ó δ: {qi,x,qj | qi 〖,q〗j ∈Q;x∈∑} - (del estado qi mediante el terminal x se va a qj  ), es la función de transición. 

Este tipo de autómatas se diferencia de los AFD, básicamente en como puede constituirse la función de transición:. Esta diferencias son las siguientes: