Autómata finito no determinista

 ¿Qué es?

Un autómata finito “no determinista” (AFN) tiene la capacidad de estar en varios estados a la vez. Esta capacidad a menudo se expresa como la posibilidad de que el autómata “conjeture” algo acerca de su entrada.

Una transición puede llevar a múltiples estados.

Construcción

Un AFN se representa esencialmente como un AFD: 

A = (Q,Σ,δ,q0,F) 

donde:

 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. 

Lenguaje

Un AFN acepta una cadena w si es posible elegir cualquier secuencia de opciones del estado siguiente, a medida que se leen los caracteres de w, y se pasa del estado inicial a cualquier estado de aceptación. El hecho de que otras opciones que empleen los símbolos de entrada de w lleven a un estado de no aceptación, o no lleven a ningún estado en absoluto (es decir, la secuencia de estados “muertos”), no impide que w sea aceptada por el AFN como un todo.

EJ.