Automata finitos no derteminista.

Definicion.

Este tipo de autómatas 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. Por ejemplo, cuando el autómata se utiliza para buscar determinadas secuencias de caracteres (por ejemplo, palabras clave) dentro de una cadena de texto larga, resulta útil “conjeturar” que estamos al principio de una de estas cadenas y utilizar una secuencia de estados únicamente para comprobar la aparición de la cadena, carácter por carácter.

Los AFN son definiciones no tan deseables dentro de los Lenguajes Regulares (LR) porque dificultan 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 Autómatas Finitos (AF), y gramáticas regulares a AF) conducen a AFN. Los AFN, por tanto, son imprescindibles en el análisis lexicográfico y el diseño de los lenguajes de programación.

Punto de vista informal de los autómatas finitos no deterministas.

Al igual que el AFD, un AFN tiene un conjunto finito de estados, un conjunto finito de símbolos de entrada, un estado inicial y un conjunto de estados de aceptación. También dispone de una función de transición, que denominaremos normalmenteδ . La diferencia entre los AFD y los AFN se encuentra en el tipo de función δ . En los AFN, δ es una función que toma un estado y símbolos de entrada como argumentos (al igual que la función de transición delAFD), pero devuelve un conjunto de cero, uno omás estados.

El lenguaje de un AFN. 

Como hemos sugerido, 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.

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

 

Ejemplo