Autómata finito no determinista
El autómata finito que presentamos en los capítulos anteriores (lo abreviamos AF o AFD) era siempre determinista, lo que se manifestaba en que en cada momento estaba claro qué haría el autómata. Ahora veamos un concepto más general, el de los autómatas finitos no deterministas (los abreviamos AFND), en los que pueden existir transiciones que salen del mismo estado y corresponden al mismo símbolo.
Ejemplo
Observa el siguiente diagrama de estados de un autómata:
¿Qué tiene de especial? Que del nodo q0 salen dos aristas para el símbolo 0. Si intentamos aceptar la palabra 001, parecería que el autómata no sabrá si debe quedarse en el estado q0 o seguir la transición hacia q1. Un autómata así sería no determinista.
El determinismo, en este sentido, significa que en cada situación está claro qué hará el autómata y no hay lugar para la ambigüedad. Un autómata determinista tiene para cada estado y cada símbolo una sola transición. El no determinismo implica ambigüedad: de un estado pueden salir, por ejemplo, tres transiciones para el mismo símbolo.
¿Y cómo decide entonces el autómata? Un autómata no determinista elige siempre (a veces también se dice que «adivina») la transición que lleva a aceptar la palabra, siempre que sea posible.
Si introducimos en el autómata la palabra 001, el autómata tiene estas posibilidades de tratar la palabra:
además de las posibilidades en las que no lee la palabra entera. En la primera se quedaba siempre en el estado q0, algo que sin duda puede hacer, porque las reglas de transición lo permiten. En la segunda rama se atrevió a pasar a otros estados y al final llegó al estado q2, que es final. En esta rama el autómata aceptaría la palabra. Un autómata no determinista elige automáticamente la rama en la que acepta la palabra, si existe tal rama.
¿Cómo logra elegir automáticamente la rama «favorable»? Podemos imaginarlo así: el autómata no determinista recorre todas las ramas posibles y, si encuentra una rama en la que acepta la palabra, entonces acepta la palabra. ¿Cómo podría recorrer todas las ramas? Sencillamente, cuando está en un estado del que salen n aristas para el símbolo actual, el autómata se copia a sí mismo n veces y cada copia sigue un camino distinto. De este modo vamos recorriendo todas las posibilidades.
Representación en forma de árbol del cómputo del autómata
Modifiquemos ligeramente el autómata anterior:
El no determinismo sigue estando en el primer estado. El autómata anterior aceptaba todas las palabras que terminan en 01. Este autómata modificado acepta todas las palabras que contienen la subpalabra 01. Por tanto, acepta, por ejemplo, la palabra 101 o 0101. Todas las ramas del cómputo se pueden visualizar fácilmente con un árbol; por ejemplo, para la palabra 01010 el árbol podría tener este aspecto:
Al principio estamos en el estado inicial q0. En la entrada tenemos la palabra 01010 y el primer símbolo sin leer es 0. Del estado q0 salen dos transiciones para el símbolo 0, hacia los estados q0 y q1. Así, el árbol tendrá en este nodo dos hijos: q0 y q1. A continuación leemos el símbolo 1. Aquí no hay ninguna ambigüedad y pasamos a los estados q0 y q2. Después leemos el símbolo 0; en la rama izquierda vuelve a haber ambigüedad y dividimos el cómputo en otras dos ramas. En una volvemos a quedarnos en q0 y en la otra pasamos a q1. Y así sucesivamente.
Fíjate en que en total dos ramas terminan en el estado q2, que es un estado final. Existen dos ramas del cómputo mediante las cuales el autómata puede aceptar la palabra dada. Por tanto, este autómata aceptaría la palabra 01010. Podemos intentar construir un árbol análogo para la palabra 1000.
El cómputo o bien se queda en el estado q0 o bien pasa al estado q1, pero desde allí ya no tiene adónde ir, porque en la entrada quedan solo ceros y el estado q1 tiene transición únicamente para el símbolo 1. Ninguna rama del cómputo termina en un estado final, así que el autómata no acepta la palabra 1000.
Transiciones ε
En los autómatas no deterministas podemos usar además transiciones ε. Son transiciones que podemos realizar sea cual sea el símbolo que haya en la entrada, y además sin leer ningún símbolo de la palabra. ¿Cómo podríamos escribir un autómata no determinista que aceptara la palabra vacía, todas las palabras formadas solo por unos y las palabras de la forma (10)n, es decir, 10, 1010, …?
Hemos dividido el autómata en dos «subautómatas». El de arriba se encarga de reconocer las palabras formadas por unos y el de abajo se encarga de las palabras de la forma (10)n. Intentemos aceptar la palabra 111. Al principio el autómata se encuentra en el estado q0 y en la entrada tiene la palabra 111. Como dispone de transiciones ε, puede decidir pasar al estado q1 o q2 según le convenga. Vemos que le conviene pasar al estado q1. El autómata pasa allí. ¡Y en la entrada sigue teniendo la palabra 111! Solo en ese momento empieza a leer los símbolos de la palabra y a pasar de q1 otra vez a q1, hasta que lee la palabra entera y la acepta.
Si intentáramos aceptar 1010, el autómata pasaría al principio al estado q2 y solo desde allí empezaría a procesar los símbolos y de nuevo aceptaría la palabra.
Para la palabra 1100 el autómata podría hacer lo que quisiera: no tiene manera de aceptarla.
Las transiciones ε y el no determinismo nos facilitan el trabajo en muchos aspectos; por ejemplo, la demostración de que la unión de lenguajes regulares es de nuevo un lenguaje regular se puede escribir con transiciones ε de forma mucho más sencilla que en el caso de los autómatas finitos deterministas. En esa demostración teníamos ejemplos de estos autómatas
y
y a continuación construimos un autómata finito determinista que aceptaba la unión de ambos lenguajes. Con transiciones ε podemos construir un autómata así de este modo:
Basta con añadir un nuevo estado inicial, del que salen dos transiciones ε hacia los estados iniciales de los autómatas originales, y eso es todo. El autómata decide de forma no determinista si intentará aceptar la palabra con uno u otro «subautómata».
Definición de autómata no determinista
Ya hemos mostrado en qué se diferencian un autómata finito determinista y uno no determinista; solo falta formalizarlo. Definimos el autómata finito determinista como una quíntupla ⟨Q, Σ, δ, q0, F⟩, donde Q es el conjunto de estados, Σ es el alfabeto, δ es la función de transición, q0 es el estado inicial y F es el conjunto de estados finales. Lo único que cambia en la definición de los autómatas no deterministas es la definición de la función de transición.
En la versión determinista, la función al llamar a δ(q, w) podía devolver un solo estado, mientras que en la versión no determinista puede devolver varios estados, si para un símbolo hay definidas varias transiciones. Como necesitamos definir también las transiciones ε, designamos el conjunto Σ ∪ {ε} como el conjunto Σε, es decir, Σε = Σ ∪ {ε}. Así, definimos la función δ como
Aquí 2Q denota el conjunto potencia, el conjunto de todos los subconjuntos del conjunto Q. La formalización del cómputo es muy parecida a la de los autómatas finitos. La configuración del autómata es de nuevo un par ⟨q, w⟩ ∈ Q × Σ∗. El paso de cómputo ↦ es una relación en el conjunto de las configuraciones tal que
si y solo si qj ∈ δ(qi, w0). En esta frase estaba la mayor diferencia. En los autómatas deterministas teníamos esta condición escrita como qj = δ(qi, w0), porque la función δ devolvía siempre un solo estado. La versión no determinista de la función de transición devuelve un conjunto de estados, y por eso aparece el símbolo ∈. La clausura reflexiva y transitiva de la relación la denotaremos de nuevo ↦ ∗. Decimos que el autómata acepta la palabra w si y solo si existe un qf ∈ F tal que
Fuentes
Capítulos: Autómata finito, Autómata completo, Autómata finito no determinista, Simulación de un autómata finito no determinista, Conversión de un AFND en un AFD
