Características del autómata finito no determinista

 

Definición de autómata finito no determinista

Es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible. Todo AFND puede ser convertido en un AFD equivalente.

Autómatas finitos no deterministas

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.

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

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.

Características

 

1. Tiene un conjunto finito de estados.

 

2. Consta de un conjunto finito de símbolos de entrada

 

3. Tiene un estado inicial y un conjunto de estados de aceptación.

 

4. También dispone de una función de transición, que denominaremos normalmente δ.

 

Donde δ es una función que toma un estado y símbolos de entrada como argumentos (al igual que la función de transición del AFD), pero devuelve un conjunto de cero, uno o más estados (en lugar de devolver exactamente un estado.

Como procesa cadenas

 

El texto de un documento se introduce carácter a carácter en este AFN, el cual reconoce a continuación las apariciones de las palabras clave en dicho texto. Existe una forma simple para que un AFN reconozca un conjunto de palabras clave.

 

1. Hay un estado inicial con una transición a sí mismo para cada uno de los símbolos de entrada, por ejemplo, todos los caracteres ASCII imprimibles si estamos examinando texto. Intuitivamente, el estado inicial representa una “conjetura” de que todavía no hemos detectado una de las palabras clave, incluso aunque hayamos encontrado algunas de las letras de una de esas palabras.

 

2. Para cada palabra clave a1a2 ···ak, existen k estados, por ejemplo, q1,q2,...,qk. Existe una transición desde el estado inicial a q1 para el símbolo a1, una transición desde q1 a q2 para el símbolo a2, etc. El estado qk es un estado de aceptación e indica que se ha encontrado la palabra clave a1a2 ···ak.

Diagrama de transiciones

 

Ejemplo: Suponga que deseamos diseñar un AFN para reconocer las apariciones de las palabras web y ebay. El diagrama de transiciones para el AFN diseñado utilizando las reglas anteriores se muestra en la Figura 2.16. El estado 1 es el estado inicial y utilizamos Σ para definir el conjunto de todos los caracteres ASCII imprimibles. Los estados 2 hasta 4 tienen que reconocer la palabra web, mientras que los estados 5 hasta 8 tienen el trabajo de reconocer la palabra ebay.

Video