Conversión de un AFND en un AFD

Veremos cómo convertir un autómata no determinista en un autómata determinista, con lo que demostraremos que la potencia de los autómatas no deterministas y la de los deterministas es equivalente.

Idea básica

Tomemos un autómata no determinista ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ sin transiciones ε. Construimos un autómata determinista ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ de modo que

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D  ∣  Q ∩ F_N ≠ ∅}

La función de transición δ_D la definimos de la siguiente manera:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

¿Qué significa esto? Un autómata no determinista puede estar a la vez en varios estados, de modo que, por ejemplo, podemos llegar a una situación en la que nuestro autómata no determinista está en los estados {q₀, q₁}. Al leer el símbolo siguiente, por ejemplo 1, podemos pasar al conjunto de estados {q₀, q₂, q₃}. En la versión determinista del mismo autómata esto se refleja así: creamos dos estados, los nombramos {q₀, q₁} y {q₀, q₂, q₃} e introducimos entre ellos una transición para el símbolo 1. Formalmente pasamos de un estado a otro, pero gracias al nombre sabremos que en el autómata no determinista nos encontraríamos en dos o en tres estados, respectivamente.

Ejemplo

Tomemos este autómata no determinista:

Para construir el autómata determinista necesitamos, ante todo, construir una nueva función de transición. Nos ayudará una tabla en la que anotaremos todas las transiciones. Al principio la tabla tiene este aspecto:

$$\begin{array}{ccc}\text{estado}/\text{símbolo}& 0& 1\\ \left\{q_0\right\}\end{array}$$

En la columna de la izquierda tendremos al final del algoritmo todos los estados del autómata determinista. La tabla rellena nos determinará la función de transición. Ahora anotamos en la tabla a qué estados llegamos si estamos en el estado {q₀} y en la entrada están los símbolos 0 y 1.

$$\begin{array}{ccc}\text{estado}/\text{símbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Del estado q₀ sale para el símbolo 0 una transición solo al estado q₁, mientras que para el símbolo 1 sale a los estados q₁ y q₂. Ahora añadimos a la tabla dos estados nuevos: {q₁} y {q₁, q₂}. ¿Por qué? Cada vez que completamos la tabla con un conjunto de estados que todavía no tenemos en la columna de la izquierda, añadimos ese conjunto de estados allí.

$$\begin{array}{ccc}\text{estado}/\text{símbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

y de nuevo rellenamos. En el estado {q₁, q₂} no debemos olvidar comprobar los dos estados, es decir, unir los estados a los que llegamos desde el estado q₁ con aquellos a los que llegamos desde el estado q₂.

$$\begin{array}{ccc}\text{estado}/\text{símbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Hemos obtenido varios estados nuevos, que debemos añadir a la tabla:

$$\begin{array}{ccc}\text{estado}/\text{símbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…y otra vez completamos las transiciones:

$$\begin{array}{ccc}\text{estado}/\text{símbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Los estados {q₀, q₁, q₃}, {q₁} y {q₁,q₂} ya los tenemos, así que solo añadimos el estado {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{estado}/\text{símbolo}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

No hemos añadido ningún estado nuevo, así que la tabla está rellena. Ahora solo falta construir el diagrama de estados. Los estados del autómata determinista están en la primera columna y las transiciones para los símbolos 0 y 1 en las siguientes. Todo estado que contenga algún estado final del autómata original será también estado final en este autómata. Es decir, todo estado que contenga q₃ será un estado final. El autómata quedará así:

Podemos comprobar que el autómata funciona realmente bien. Intentemos aceptar la palabra 11001. En el autómata determinista seguiremos el camino

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

y el autómata aceptaría la palabra, porque el último estado {q₀, q₁, q₂, q₃} es final. En el autómata no determinista llegaríamos durante la simulación a los mismos estados, es decir, empezaríamos en el estado q₀ y para el símbolo 1 llegaríamos a los estados {q₁, q₂}. El siguiente símbolo 1 nos llevaría a los estados {q₀,q₃} y así sucesivamente con los demás estados. Al final nos encontraríamos en todos los estados {q₀, q₁, q₂, q₃} y el autómata aceptaría la palabra.

Fuentes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools