Simulación de un autómata finito no determinista

Si tenemos un autómata no determinista y queremos averiguar si acepta una palabra dada, podemos convertir el autómata en determinista, podemos probar de alguna manera o podemos usar un algoritmo que simule el funcionamiento del AFND.

Principio del algoritmo

Mostraremos el principio con un ejemplo adecuado. Tomemos este autómata:

Se trata de un autómata finito no determinista que acepta cierto lenguaje. Ahora mismo no nos interesa en absoluto cuál. Veremos cómo puede ser el cómputo de un autómata así para la palabra de entrada 11001. El razonamiento será este: procesamos un símbolo de la palabra y miramos adónde podemos ir gracias a las transiciones múltiples para el mismo símbolo. Guardamos todos esos estados y en el paso siguiente supondremos que estamos «en todos esos estados a la vez» y nos interesará adónde podemos llegar desde ellos.

Así, iremos guardando el conjunto de estados en los que podemos encontrarnos y la parte sin leer de la palabra. Al principio tenemos el par ⟨{q₀}, 11001⟩. Empezamos en el estado q₀ (estado inicial) y en la entrada está la palabra 11001. El autómata queda así; en rojo y en negrita está resaltado el estado en el que estamos:

El primer símbolo es 1; desde el estado q₀ hay una sola transición para el símbolo 1, así que llegamos al estado q₁. Anotamos el par ⟨{q₁}, 1001⟩. El autómata queda así:

Continuamos. La parte sin leer de la palabra es 1001, así que de nuevo buscamos transiciones para 1. Ahora son dos: de vuelta al estado q₀ y también al estado q₃. Ahora iremos a ambos estados a la vez. Anotamos así el par ⟨{q₀, q₃}, 001⟩.

¿Qué lógica tiene esto? Sabemos que existe un camino para llegar desde el estado inicial, con la palabra 11, tanto al estado q₃ como al estado q₀. Todavía no sabemos qué rama nos convendrá, así que sencillamente guardamos ambas. Continuamos. En la entrada tenemos el símbolo 0. Ahora debemos mirar tanto las transiciones desde q₀ como las transiciones desde q₃. Del estado q₀ salen transiciones hacia los estados q₁ y q₂, y del estado q₃ sale una transición de vuelta a q₁. Juntamos todos estos estados y obtenemos el par ⟨{q₁, q₂}, 01⟩:

Pero en este paso todavía no hemos terminado. Vemos que del estado q₂ sale una transición ε hacia el estado q₄. Sabemos que por una transición ε podemos pasar «en cualquier momento», sin leer otro símbolo. Dicho de otro modo, sin leer otro símbolo de la palabra de entrada, todavía podemos pasar al estado q₄. Así añadimos el estado q₄ a los estados en los que podemos encontrarnos: ⟨{q₁, q₂, q₄}, 01⟩. Colorearíamos el autómata así:

A continuación, en la entrada hay un 0. Miramos adónde podemos pasar desde esos tres estados en los que estamos. Desde q₁ no podemos pasar a ninguna parte, porque falta la transición para 0. El cómputo en esta rama termina. Desde el estado q₄ tampoco llegamos a ninguna parte. Desde el estado q₂ llegamos de vuelta al estado q₂. Pero como desde el estado q₂ sale de nuevo una transición ε hacia el estado q₄, podemos llegar también al estado q₄. Así, desde el conjunto de estados {q₁, q₂, q₄} para el símbolo 0 podemos llegar al conjunto de estados {q₂, q₄} y obtenemos el par ⟨{q₂, q₄}, 1⟩:

Por último, en la entrada tenemos el símbolo 1. Desde q₂ no llegamos a ninguna parte y el cómputo en esta rama termina. Desde q₄, en cambio, llegamos a los estados q₃ y q₅. Obtenemos el par ⟨{q₃, q₅}, ε⟩:

El autómata ha leído ya la palabra entera y «se encuentra» en dos estados: q₃, q₅. Como al menos uno de ellos es un estado final, el autómata acepta la palabra 11001.

Algoritmo

Lo primero que necesitamos es una función que tome como parámetro un conjunto de estados y calcule a qué estados podemos llegar además mediante transiciones ε. La entrada es, por tanto, el autómata ⟨Q, Σ, δ, q₀, F⟩ y un conjunto de estados States, y la salida es un superconjunto de esos estados, formado por los estados a los que se puede llegar mediante transiciones ε. A esta operación la llamaremos clausura ε del conjunto States.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Usaremos esta función en la función que simulará el funcionamiento del autómata no determinista. La entrada es el autómata, la palabra de entrada w = w₁w₂… w_n y el conjunto de estados en los que se encuentra el autómata en ese momento. La salida es la respuesta SÍ o NO, según el autómata acepte o no la palabra dada.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return SÍ \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Si queremos comprobar si el autómata acepta la palabra w, llamamos a la función así: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

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

« Anterior: Autómata finito no determinista

Siguiente: Conversión de un AFND en un AFD »