Tamaño de letra
Tema
Ancho de lectura
Tipografía

Apuntes · Capítulo 2Lenguajes regulares

No determinismo

No determinismo

La semana pasada definimos el autómata finito determinista (DFA): en cada estado, con cada símbolo, hay exactamente una flecha que seguir. Con esa máquina diseñamos reconocedores, demostramos que eran correctos y vimos que los lenguajes regulares son cerrados bajo unión, intersección y complemento. Quedaron dos operaciones sin tocar, la concatenación y la estrella, y no fue por descuido: con un DFA no se ve cómo hacerlas. Para reconocer ABAB habría que saber dónde termina el trozo de AA y empieza el de BB, y un DFA lee la entrada una sola vez, sin poder probar varios cortes.

Esta semana le damos a la máquina una capacidad que parece trampa: elegir. Un autómata finito no determinista (NFA) puede tener, desde un estado y con un símbolo, varias flechas, o ninguna, y puede cambiar de estado sin leer nada. Acepta una cadena si alguna manera de elegir lo lleva a un estado de aceptación. Con esa libertad, los diseños que costaban salen cortos, y la concatenación y la estrella se construyen en dos líneas.

La sorpresa de la semana es que la capacidad nueva no agrega ningún lenguaje. Todo NFA se puede convertir en un DFA que reconoce exactamente lo mismo, con la construcción de subconjuntos. El no determinismo es entonces una herramienta para diseñar y para demostrar, y el precio de quitarlo está en la cantidad de estados, que puede crecer exponencialmente. La misma pregunta, cuánto cuesta simular a una máquina que adivina con una que no adivina, vuelve al final del curso con las máquinas de Turing y el tiempo: ahí es la pregunta de si P es igual a NP, y nadie conoce la respuesta. Aquí sí la vamos a conocer completa.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Un diseño que con un DFA cuesta y Qué cambia en un NFA. Antes de la sesión B, La construcción de subconjuntos hasta el primer ejemplo. Con eso llegan con el primer NFA ya visto y con la idea de la construcción.

En clase: Sesión A, de Un diseño que con un DFA cuesta a Todo DFA es un NFA. Sesión B, de La construcción de subconjuntos a El complemento no se hace en el NFA.

Después de clase: el Resumen y los Ejercicios, para repasar. Antes del laboratorio, La clausura ε, La construcción de subconjuntos otra vez y El código de la semana. Para ampliar, las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, sec. 1.2 (Nondeterminism), completa: la definición formal, Equivalence of NFAs and DFAs y Closure under the regular operations. Erickson, Models of Computation, nota 4 (Nondeterministic automata). Son apoyo: estos apuntes se pueden estudiar solos.

Código. Los programas de este capítulo están en code/week-02. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. El laboratorio está en lab/nfa_to_dfa.

Un diseño que con un DFA cuesta

Lenguaje.

T={ w∈{0,1}∗:el tercer sıˊmbolo de w desde el final es 1 }T = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : \text{el tercer símbolo de } w \text{ desde el final es } \mathtt{1} \,\}

Las cadenas 100\mathtt{100}, 0110\mathtt{0110} y 1111\mathtt{1111} están en TT. Las cadenas 011\mathtt{011}, 0010\mathtt{0010} y todas las de longitud menor que 3 no están.

Apliquemos el método de la semana pasada: ponerse en el lugar de la máquina y decidir qué recordar. Los símbolos llegan de uno en uno y en cualquier momento pueden decir “ahí terminó”. Cuando llega un 1\mathtt{1}, la máquina no sabe si ese será el tercero desde el final: depende de cuántos símbolos falten, y eso no lo ve. Para poder responder siempre, tiene que recordar los tres últimos símbolos que leyó, completos. Hay 23=82^3 = 8 combinaciones, y hace falta un estado por cada una: un DFA de 8 estados y 16 transiciones. Las cadenas de menos de tres símbolos se acomodan en los mismos estados, como si antes de ellas hubiera ceros. Se puede hacer, y más abajo lo va a construir un programa. Pero el diseño no se parece a la descripción del lenguaje, y si en lugar del tercero fuera el décimo símbolo desde el final, serían 210=10242^{10} = 1024 estados.

Ahora supongan que la máquina pudiera adivinar. Lee símbolos sin hacer nada, y cuando llega un 1\mathtt{1} puede apostar: “este es el tercero desde el final”. Para comprobar la apuesta solo tiene que leer dos símbolos más, cualesquiera, y ver que ahí se acaba la cadena. Eso son cuatro estados:

Arriba, el diagrama del NFA, con cuatro estados en fila: q₀, q₁, q₂ y q₃. La flecha de inicio entra a q₀, que tiene un bucle con 0 y con 1 y una flecha con 1 hacia q₁. De q₁ sale una flecha con 0 y con 1 hacia q₂, y de q₂ otra con 0 y con 1 hacia q₃, que tiene doble círculo. Debajo de cada estado, lo que significa: en q₀ todavía no apostó; en q₁ apostó que este 1 es el tercero desde el final; en q₂ leyó un símbolo más después de la apuesta; en q₃ leyó dos más y la cadena tiene que acabar aquí. Dos notas: de q₀ salen dos flechas con 1, y de q₃ no sale ninguna. Abajo, los ocho estados de un DFA para el mismo lenguaje, uno por cada combinación de los tres últimos símbolos, de 000 a 111, sin sus 16 transiciones; los cuatro que empiezan con 1 son de aceptación. Para el décimo símbolo desde el final, el NFA tendría 11 estados y el DFA 1024Arriba, el diagrama del NFA, con cuatro estados en fila: q₀, q₁, q₂ y q₃. La flecha de inicio entra a q₀, que tiene un bucle con 0 y con 1 y una flecha con 1 hacia q₁. De q₁ sale una flecha con 0 y con 1 hacia q₂, y de q₂ otra con 0 y con 1 hacia q₃, que tiene doble círculo. Debajo de cada estado, lo que significa: en q₀ todavía no apostó; en q₁ apostó que este 1 es el tercero desde el final; en q₂ leyó un símbolo más después de la apuesta; en q₃ leyó dos más y la cadena tiene que acabar aquí. Dos notas: de q₀ salen dos flechas con 1, y de q₃ no sale ninguna. Abajo, los ocho estados de un DFA para el mismo lenguaje, uno por cada combinación de los tres últimos símbolos, de 000 a 111, sin sus 16 transiciones; los cuatro que empiezan con 1 son de aceptación. Para el décimo símbolo desde el final, el NFA tendría 11 estados y el DFA 1024
La máquina que adivina necesita cuatro estados. La que no adivina tiene que recordar los tres últimos símbolos: ocho estados.
Estado Lo que significa
q0q_0 Todavía no apostó
q1q_1 Apostó: el 1\mathtt{1} que acaba de leer es el tercero desde el final
q2q_2 Después de la apuesta leyó un símbolo más
q3q_3 Después de la apuesta leyó dos símbolos más: si la cadena termina aquí, la apuesta era correcta

Este dibujo no es un DFA, por dos razones. Del estado q0q_0 salen dos flechas con 1\mathtt{1}: una que vuelve a q0q_0 y otra que va a q1q_1. Y del estado q3q_3 no sale ninguna. Es un autómata finito no determinista, y es la máquina de esta semana.

Qué cambia en un NFA

Un NFA se dibuja igual que un DFA: círculos, flechas con etiquetas, una flecha de entrada para el estado inicial y doble círculo para los estados de aceptación. Cambian tres reglas sobre las flechas.

  1. Varias flechas con el mismo símbolo. Desde un estado, con un símbolo, puede haber más de un destino. La máquina puede seguir cualquiera de ellos.
  2. Ninguna flecha. Desde un estado puede no haber flecha con algún símbolo. Si la máquina está ahí y llega ese símbolo, ese intento se acaba: decimos que el camino muere. No hace falta estado trampa.
  3. Flechas sin símbolo. Una flecha puede llevar la etiqueta ε\varepsilon. La máquina puede seguirla sin leer nada de la entrada. Se llaman transiciones ε\varepsilon (ε-transitions) y aparecen dos secciones más abajo.

Y cambia qué significa aceptar. En un DFA la cadena determina un solo recorrido. En un NFA, una misma cadena puede tener muchos recorridos, según qué flecha se elija en cada paso, y algunos terminan en un estado de aceptación y otros no.

Idea clave. Un NFA acepta una cadena si existe al menos un camino que lee la cadena completa y termina en un estado de aceptación. No importa cuántos otros caminos mueran o terminen en otro lado. La rechaza solo si ningún camino lo logra.

El autómata del dibujo está en machines/third_from_end.nfa, en el formato .nfa de code/formats.md:

# El tercer símbolo desde el final es 1.
# q0: espera. q1: adivinó que el 1 que acaba de leer es el tercero desde el final.
# q2: leyó un símbolo más. q3: leyó dos más.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 1 q2
q2 0 q3
q2 1 q3

El formato es el de la semana pasada con dos diferencias. Una línea de delta: puede tener varios destinos: q0 1 q0 q1 dice que desde q0, con 1, se puede ir a q0 o a q1. Y un par de estado y símbolo puede no tener línea: no hay ninguna para q3. El programa show_nfa muestra la máquina como tabla:

$ build/show_nfa machines/third_from_end.nfa
Q  = {q0, q1, q2, q3}
Σ  = {0, 1}
q0 = q0
F  = {q3}

     δ   0     1        ε
->   q0  {q0}  {q0,q1}  {}
     q1  {q2}  {q2}     {}
     q2  {q3}  {q3}     {}
   * q3  {}    {}       {}

no tiene transiciones ε: E(S) = S para todo conjunto S

En la tabla de un DFA cada casilla era un estado. Aquí cada casilla es un conjunto de estados: todos los destinos posibles. Los programas del capítulo escriben {} para el conjunto vacío ∅\emptyset. La fila de q3 es toda {}: de ahí no sale nada. La columna ε está vacía porque esta máquina no tiene transiciones ε\varepsilon. La última línea habla de E(S)E(S), la clausura ε\varepsilon, que se define más abajo.

Sigamos la máquina a mano con w=0110w = \mathtt{0110}. En q0q_0, el primer 0\mathtt{0} solo permite quedarse. Con el primer 1\mathtt{1} hay que elegir: quedarse en q0q_0 o apostar y pasar a q1q_1. Si la máquina apuesta ahí, lee el segundo 1\mathtt{1} y pasa a q2q_2, lee el 0\mathtt{0} y pasa a q3q_3, y la cadena se acabó: está en un estado de aceptación. Ese es un camino que acepta, y con uno basta: 0110∈T\mathtt{0110} \in T. En efecto, el tercer símbolo desde el final de 0110\mathtt{0110} es el primer 1\mathtt{1}.

Tres maneras de pensar el no determinismo

Una máquina real no adivina. El no determinismo es una definición matemática, y hay tres imágenes que ayudan a razonar con ella. Las tres dicen lo mismo, y conviene saber pasar de una a otra.

Adivinar bien. La máquina tiene suerte perfecta: cada vez que hay varias flechas, elige la que lleva a aceptar, si alguna lleva. Es la imagen más cómoda para diseñar: uno piensa “la máquina adivina dónde está el tercer símbolo desde el final, y después comprueba”. El NFA no necesita saber cómo adivinar. Solo necesita que, cuando la cadena está en el lenguaje, haya una adivinanza que funcione, y que cuando no está, ninguna adivinanza pueda engañarlo. La segunda mitad es la que se olvida: una apuesta equivocada no puede terminar en aceptación.

Explorar todos los caminos a la vez. Cada vez que hay varias flechas, la máquina se copia a sí misma y cada copia sigue una. Una copia que no tiene flecha con el símbolo que llega desaparece. Al final de la cadena, si alguna copia está en un estado de aceptación, la cadena se acepta. Como dos copias en el mismo estado hacen lo mismo de ahí en adelante, no hace falta contarlas: basta saber en qué estados hay alguna copia. Ese conjunto de estados es lo que un programa lleva para simular un NFA, y es la idea de la sesión B.

Un árbol de ejecuciones. La raíz es el estado inicial. Cada nodo tiene un hijo por cada flecha que puede seguir con el símbolo que toca. El DFA era el caso en que el árbol es una sola rama. La cadena se acepta si alguna hoja, al nivel del final de la cadena, es un estado de aceptación.

El programa paths_nfa escribe el árbol rama por rama, cada una desde la raíz:

$ build/paths_nfa machines/third_from_end.nfa 0110
w = 0110
  q0 -0-> q0 -1-> q0 -1-> q0 -0-> q0    termina en q0, que no está en F
  q0 -0-> q0 -1-> q0 -1-> q1 -0-> q2    termina en q2, que no está en F
  q0 -0-> q0 -1-> q1 -1-> q2 -0-> q3    termina en q3, que está en F
caminos que leen toda la cadena: 3    que mueren antes: 0    que terminan en F: 1
algún camino termina en F: acepta

Hay tres caminos, uno por cada decisión posible: no apostar nunca, apostar en el segundo 1\mathtt{1} o apostar en el primero. Solo el último acepta. El segundo apostó tarde: la cadena se acabó antes de llegar a q3q_3. Con 1100\mathtt{1100} se ve la otra manera de equivocarse:

$ build/paths_nfa machines/third_from_end.nfa 1100
w = 1100
  q0 -1-> q0 -1-> q0 -0-> q0 -0-> q0    termina en q0, que no está en F
  q0 -1-> q0 -1-> q1 -0-> q2 -0-> q3    termina en q3, que está en F
  q0 -1-> q1 -1-> q2 -0-> q3    muere: q3 no tiene transición con 0
caminos que leen toda la cadena: 2    que mueren antes: 1    que terminan en F: 1
algún camino termina en F: acepta

El tercer camino apostó demasiado pronto. Llegó a q3q_3 cuando todavía faltaba un símbolo, y como de q3q_3 no sale ninguna flecha, murió. Pasó por un estado de aceptación y no cuenta: igual que en un DFA, solo importa dónde se está cuando la cadena se acaba. Por eso q3q_3 no tiene flechas de salida: es lo que obliga a que la apuesta sea exacta.

Árbol de ejecuciones del NFA con la cadena 1100, dibujado de izquierda a derecha, con una columna por cada prefijo leído: ε, 1, 11, 110 y 1100. La raíz es q₀. La rama de arriba no apuesta nunca: q₀, q₀, q₀, q₀, q₀, y termina en q₀, que no está en F. Del segundo q₀ de esa rama sale la rama del medio, que apuesta en el segundo 1: q₁, q₂ y q₃; termina en q₃, que está en F, y es la que hace que la cadena se acepte. De la raíz sale la rama de abajo, que apuesta en el primer 1: q₁, q₂ y q₃ después de leer 110; ahí queda un 0 por leer, q₃ no tiene transición con 0, y la rama muere, marcada con una equis. Una nota junto a ese q₃ dice que pasó por q₃ y no cuenta. La última columna, la del final de la cadena, está recuadrada: solo cuenta lo que hay en ellaÁrbol de ejecuciones del NFA con la cadena 1100, dibujado de izquierda a derecha, con una columna por cada prefijo leído: ε, 1, 11, 110 y 1100. La raíz es q₀. La rama de arriba no apuesta nunca: q₀, q₀, q₀, q₀, q₀, y termina en q₀, que no está en F. Del segundo q₀ de esa rama sale la rama del medio, que apuesta en el segundo 1: q₁, q₂ y q₃; termina en q₃, que está en F, y es la que hace que la cadena se acepte. De la raíz sale la rama de abajo, que apuesta en el primer 1: q₁, q₂ y q₃ después de leer 110; ahí queda un 0 por leer, q₃ no tiene transición con 0, y la rama muere, marcada con una equis. Una nota junto a ese q₃ dice que pasó por q₃ y no cuenta. La última columna, la del final de la cadena, está recuadrada: solo cuenta lo que hay en ella
Las tres líneas de la salida, como árbol. Para aceptar basta una hoja de aceptación en la última columna; la rama que pasó antes por q₃ no llega hasta ahí.

Error común. Creer que el NFA acepta solo si todos los caminos aceptan. Es al revés: basta uno. Con 0110\mathtt{0110}, dos de los tres caminos no aceptan, y la cadena se acepta.

Error común. Creer que el NFA “elige al azar” y que a veces acepta una cadena y a veces no. En un NFA no hay probabilidades ni suerte: que ww esté en el lenguaje es un hecho sobre la máquina y la cadena, que depende de si existe un camino. Las máquinas que de verdad lanzan monedas son otro modelo, que aparece en la semana 15.

Error común. Decir que un camino que muere “rechaza la cadena”. Un camino que muere no decide nada: solo deja de contar. La cadena se rechaza cuando no queda ningún camino que termine en aceptación.

La definición formal de un NFA

Definición. Un autómata finito no determinista (nondeterministic finite automaton), o NFA, es una quíntupla N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F), donde:

  1. QQ es un conjunto finito, el de los estados.
  2. Σ\Sigma es un alfabeto.
  3. δ:Q×(Σ∪{ε})→P(Q)\delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q) es la función de transición.
  4. q0∈Qq_0 \in Q es el estado inicial.
  5. F⊆QF \subseteq Q es el conjunto de los estados de aceptación.

Cuatro de los cinco componentes son los de un DFA. Toda la diferencia está en el tipo de δ\delta, y conviene leerlo pieza por pieza.

  • Lo que devuelve: P(Q)\mathcal{P}(Q). Es el conjunto potencia de QQ: el conjunto de todos los subconjuntos de QQ. Entonces δ(q,a)\delta(q, a) no es un estado, sino un conjunto de estados: los destinos posibles. En el ejemplo, δ(q0,1)={q0,q1}\delta(q_0, \mathtt{1}) = \{q_0, q_1\} y δ(q1,0)={q2}\delta(q_1, \mathtt{0}) = \{q_2\}.
  • El conjunto puede ser vacío. δ(q3,0)=∅\delta(q_3, \mathtt{0}) = \emptyset: no hay flecha. Así entran en la definición las reglas 1 y 2 de la sección anterior, sin casos especiales. Y δ\delta sigue siendo una función total: para cada par devuelve exactamente un conjunto, que a veces es ∅\emptyset.
  • Lo que recibe: Σ∪{ε}\Sigma \cup \{\varepsilon\}. El segundo argumento puede ser un símbolo o ε\varepsilon. δ(q,ε)\delta(q, \varepsilon) es el conjunto de estados a los que se puede pasar desde qq sin leer nada. Sipser escribe Σε\Sigma_\varepsilon para abreviar Σ∪{ε}\Sigma \cup \{\varepsilon\}.

Error común. Tratar a ε\varepsilon como un símbolo más del alfabeto. ε\varepsilon no está en Σ\Sigma y nunca aparece en la entrada: es la cadena vacía, y una transición ε\varepsilon es un paso que no consume ningún símbolo. La cadena 01\mathtt{01} tiene dos símbolos, y un camino que la lee puede tener dos pasos, o cinco si tres de ellos son transiciones ε\varepsilon.

Falta decir con la misma precisión qué es aceptar. Con un DFA bastó la función δ∗\delta^*, porque había un solo recorrido. Aquí hay que hablar de caminos.

Definición. Sean pp y rr estados de NN y ww una cadena sobre Σ\Sigma. Un camino de pp a rr con etiqueta ww es una secuencia de estados r0,r1,…,rmr_0, r_1, \ldots, r_m y una secuencia de etiquetas y1,y2,…,ymy_1, y_2, \ldots, y_m, con m≥0m \geq 0 y cada yi∈Σ∪{ε}y_i \in \Sigma \cup \{\varepsilon\}, tales que:

  1. r0=pr_0 = p y rm=rr_m = r;
  2. ri∈δ(ri−1,yi)r_i \in \delta(r_{i-1}, y_i) para cada ii de 1 a mm: cada paso sigue una flecha de la máquina;
  3. y1y2⋯ym=wy_1y_2 \cdots y_m = w: las etiquetas, concatenadas, forman ww.

En la condición 3, una etiqueta ε\varepsilon es la cadena vacía y no aporta nada a la concatenación. Por eso mm puede ser mayor que ∣w∣|w|: el camino tiene ∣w∣|w| pasos que leen un símbolo y cualquier cantidad de pasos ε\varepsilon entre ellos. El caso m=0m = 0 es el camino que no se mueve: va de pp a pp con etiqueta ε\varepsilon.

Definición. NN acepta la cadena ww si existe un camino de q0q_0 a algún estado de FF con etiqueta ww. El lenguaje de NN es

L(N)={ w∈Σ∗:N acepta w }L(N) = \{\, w \in \Sigma^* : N \text{ acepta } w \,\}

y se dice que NN reconoce L(N)L(N).

Cada línea que imprime paths_nfa y que lee toda la cadena es un camino desde q0q_0 con etiqueta ww, en el sentido de esta definición. Un camino que muere no lo es: sus etiquetas forman solo un prefijo de ww.

En C++. El struct Nfa de nfa.h es el struct Dfa de la semana pasada con un solo tipo cambiado. El valor de delta ya no es un estado, sino un conjunto:

using StateSet = std::set<std::string>;

struct Nfa {
    std::vector<std::string> states;                         // Q, en el orden del archivo
    std::vector<char> alphabet;                              // Σ
    std::map<std::pair<std::string, char>, StateSet> delta;  // δ : Q × (Σ ∪ {ε}) → P(Q)
    std::string start;                                       // q0
    StateSet accept;                                         // F ⊆ Q
};

Una clave que no está en el mapa vale ∅\emptyset: la función delta_of(n, q, a) devuelve el conjunto guardado o uno vacío. Para ε\varepsilon se usa la constante EPS, un carácter que ningún archivo puede tener como símbolo. A diferencia de check_dfa, la función check_nfa no exige que haya una línea por cada par.

Transiciones ε

Una transición ε\varepsilon deja que la máquina cambie de estado sin leer. Sirve para decir “aquí se puede saltar esta parte” o “aquí se puede pasar a otra máquina”, y es la pieza con la que se arman todas las construcciones de la sesión B.

Lenguaje. U={ w∈{0,1}∗:w contiene 101 o contiene 11 }U = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : w \text{ contiene } \mathtt{101} \text{ o contiene } \mathtt{11} \,\}.

La semana pasada, el DFA de Contiene 101 pidió cuidado: en cada estado había que pensar cuánto de lo leído servía para un intento nuevo cuando el actual fallaba. Con un NFA no hace falta. La máquina adivina dónde empieza el patrón, lo comprueba símbolo por símbolo, y si se equivocó, ese camino muere y no pasa nada. Los dos patrones, 101\mathtt{101} y 11\mathtt{11}, se diferencian en que el segundo no tiene el 0\mathtt{0} del medio: una transición ε\varepsilon permite saltárselo.

Diagrama de estados con cuatro estados en fila: q₀, q₁, q₂ y q₃. La flecha de inicio entra a q₀, que tiene un bucle con 0 y con 1 y una flecha con 1 hacia q₁. De q₁ a q₂ van dos flechas: una por arriba con 0 y otra por abajo, punteada, con ε. De q₂ sale una flecha con 1 hacia q₃, que tiene doble círculo y un bucle con 0 y con 1. Debajo de cada estado, lo que significa: q₀ espera; en q₁ adivinó que aquí empieza el patrón y leyó su primer 1; en q₂ leyó el 0 del medio o se lo saltó con ε; en q₃ ya leyó el patrón completoDiagrama de estados con cuatro estados en fila: q₀, q₁, q₂ y q₃. La flecha de inicio entra a q₀, que tiene un bucle con 0 y con 1 y una flecha con 1 hacia q₁. De q₁ a q₂ van dos flechas: una por arriba con 0 y otra por abajo, punteada, con ε. De q₂ sale una flecha con 1 hacia q₃, que tiene doble círculo y un bucle con 0 y con 1. Debajo de cada estado, lo que significa: q₀ espera; en q₁ adivinó que aquí empieza el patrón y leyó su primer 1; en q₂ leyó el 0 del medio o se lo saltó con ε; en q₃ ya leyó el patrón completo
Las dos flechas de q₁ a q₂ son los dos patrones: con 0 se lee 101, y con ε, sin leer nada, se lee 11.
$ build/show_nfa machines/contains_101_or_11.nfa
Q  = {q0, q1, q2, q3}
Σ  = {0, 1}
q0 = q0
F  = {q3}

     δ   0     1        ε
->   q0  {q0}  {q0,q1}  {}
     q1  {q2}  {}       {q2}
     q2  {}    {q3}     {}
   * q3  {q3}  {q3}     {}

clausura ε de cada estado:
  E({q0}) = {q0}
  E({q1}) = {q1,q2}
  E({q2}) = {q2}
  E({q3}) = {q3}

En el archivo, la transición ε\varepsilon se escribe con eps en el lugar del símbolo: q1 eps q2. Desde q1q_1 hay dos maneras de llegar a q2q_2: leyendo un 0\mathtt{0}, que es el del medio de 101\mathtt{101}, o sin leer nada, que es el caso de 11\mathtt{11}. El estado q3q_3 tiene flechas hacia sí mismo: una vez visto el patrón, lo que siga no importa.

$ build/paths_nfa machines/contains_101_or_11.nfa 0101
w = 0101
  q0 -0-> q0 -1-> q0 -0-> q0 -1-> q0    termina en q0, que no está en F
  q0 -0-> q0 -1-> q0 -0-> q0 -1-> q1    termina en q1, que no está en F
  q0 -0-> q0 -1-> q0 -0-> q0 -1-> q1 -ε-> q2    termina en q2, que no está en F
  q0 -0-> q0 -1-> q1 -0-> q2 -1-> q3    termina en q3, que está en F
  q0 -0-> q0 -1-> q1 -ε-> q2    muere: q2 no tiene transición con 0
caminos que leen toda la cadena: 4    que mueren antes: 1    que terminan en F: 1
algún camino termina en F: acepta

El cuarto camino es el que acepta: apostó a que el patrón empezaba en el primer 1\mathtt{1} y leyó 101\mathtt{101}. El quinto hizo la misma apuesta pero tomó la transición ε\varepsilon, esperando un 11\mathtt{11}: llegó un 0\mathtt{0} y murió. El segundo y el tercero son la misma apuesta en el último 1\mathtt{1}, con y sin el paso ε\varepsilon final: los dos leen toda la cadena, y por eso son dos caminos distintos con la misma etiqueta.

Un segundo ejemplo, en el que las transiciones ε\varepsilon van en cadena.

Lenguaje. Sobre Σ={a,b,c}\Sigma = \{\mathtt{a}, \mathtt{b}, \mathtt{c}\}, las cadenas formadas por algunas a\mathtt{a}, después algunas b\mathtt{b} y después algunas c\mathtt{c}, donde cada bloque puede ser vacío: aacc\mathtt{aacc}, b\mathtt{b}, abc\mathtt{abc} y ε\varepsilon están; ba\mathtt{ba} y abca\mathtt{abca} no.

$ build/show_nfa machines/abc_blocks.nfa
Q  = {qa, qb, qc}
Σ  = {a, b, c}
q0 = qa
F  = {qc}

     δ   a     b     c     ε
->   qa  {qa}  {}    {}    {qb}
     qb  {}    {qb}  {}    {qc}
   * qc  {}    {}    {qc}  {}

clausura ε de cada estado:
  E({qa}) = {qa,qb,qc}
  E({qb}) = {qb,qc}
  E({qc}) = {qc}

Cada estado lee su letra, y una transición ε\varepsilon pasa al bloque siguiente. La máquina adivina cuándo se acabó cada bloque. Este autómata acepta la cadena vacía aunque su estado inicial no es de aceptación: el camino qa→qb→qcq_a \to q_b \to q_c, con dos pasos ε\varepsilon, tiene etiqueta ε\varepsilon y termina en FF.

$ build/paths_nfa machines/abc_blocks.nfa ac
w = ac
  qa -a-> qa -ε-> qb -ε-> qc -c-> qc    termina en qc, que está en F
  qa -ε-> qb -ε-> qc    muere: qc no tiene transición con a
caminos que leen toda la cadena: 1    que mueren antes: 1    que terminan en F: 1
algún camino termina en F: acepta

La clausura ε

Para seguir un NFA con transiciones ε\varepsilon hay que saber, en cada momento, a dónde se puede llegar “gratis”.

Definición. Sea S⊆QS \subseteq Q un conjunto de estados. La clausura ε\varepsilon (ε-closure) de SS es

E(S)={ r∈Q:hay un camino con etiqueta ε desde alguˊn estado de S hasta r }E(S) = \{\, r \in Q : \text{hay un camino con etiqueta } \varepsilon \text{ desde algún estado de } S \text{ hasta } r \,\}

Un camino con etiqueta ε\varepsilon es uno cuyos pasos son todos transiciones ε\varepsilon: cero pasos, uno, o varios seguidos. De la definición salen tres propiedades que usaremos sin nombrarlas.

  • S⊆E(S)S \subseteq E(S), porque el camino de cero pasos va de cada estado a sí mismo.
  • Si S⊆S′S \subseteq S', entonces E(S)⊆E(S′)E(S) \subseteq E(S').
  • E(E(S))=E(S)E(E(S)) = E(S): después de cerrar, no queda nada por agregar, porque dos caminos ε\varepsilon seguidos son un camino ε\varepsilon.

En el autómata de los bloques, E({qa})={qa,qb,qc}E(\{q_a\}) = \{q_a, q_b, q_c\}: desde qaq_a se llega a qbq_b con un paso ε\varepsilon y a qcq_c con dos. En el de Contiene 101 o 11, E({q1})={q1,q2}E(\{q_1\}) = \{q_1, q_2\} y la clausura de los demás estados no agrega nada. Si un NFA no tiene transiciones ε\varepsilon, E(S)=SE(S) = S para todo SS.

El autómata de los bloques: tres estados en fila, q_a, q_b y q_c. La flecha de inicio entra a q_a, y q_c tiene doble círculo. Cada estado tiene un bucle con su letra, a, b y c, y hay una flecha ε punteada de q_a a q_b y otra de q_b a q_c. Tres marcos, uno dentro de otro, rodean las clausuras: el más pequeño contiene solo a q_c y es E({q_c}) = {q_c}; el del medio contiene a q_b y q_c y es E({q_b}) = {q_b, q_c}; el mayor contiene a los tres y es E({q_a}) = {q_a, q_b, q_c}. Debajo: desde q_a, cero pasos ε dan q_a, un paso da q_b y dos pasos dan q_cEl autómata de los bloques: tres estados en fila, q_a, q_b y q_c. La flecha de inicio entra a q_a, y q_c tiene doble círculo. Cada estado tiene un bucle con su letra, a, b y c, y hay una flecha ε punteada de q_a a q_b y otra de q_b a q_c. Tres marcos, uno dentro de otro, rodean las clausuras: el más pequeño contiene solo a q_c y es E({q_c}) = {q_c}; el del medio contiene a q_b y q_c y es E({q_b}) = {q_b, q_c}; el mayor contiene a los tres y es E({q_a}) = {q_a, q_b, q_c}. Debajo: desde q_a, cero pasos ε dan q_a, un paso da q_b y dos pasos dan q_c
La clausura sigue todas las cadenas de flechas ε: q_c está en E({q_a}) aunque no haya flecha directa de q_a a q_c.

Error común. Seguir una sola transición ε\varepsilon y detenerse. La clausura sigue todas las cadenas de transiciones ε\varepsilon: qcq_c está en E({qa})E(\{q_a\}) aunque no haya flecha directa de qaq_a a qcq_c. El error contrario también aparece: olvidar que SS mismo está dentro de E(S)E(S).

Calcular E(S)E(S) es un problema de grafos que ya conocen. Si se dejan solo las flechas ε\varepsilon, queda un grafo dirigido, y E(S)E(S) son los vértices alcanzables desde SS. Cualquier recorrido sirve:

algoritmo clausura(N, S)
    E ← S
    pendientes ← los estados de S
    mientras pendientes no esté vacío
        q ← sacar uno de pendientes
        para cada r en δ(q, ε)
            si r no está en E entonces
                agregar r a E
                agregar r a pendientes
            fin si
        fin para
    fin mientras
    devolver E
fin algoritmo

Cada estado entra en pendientes a lo sumo una vez, así que el algoritmo termina aunque las transiciones ε\varepsilon formen un ciclo.

En C++. Es el recorrido en anchura de Algoritmos, con una cola. closure.insert(r).second es verdadero solo si r no estaba: marca el estado como visto y avisa si era nuevo, en una sola operación.

inline StateSet eps_closure(const Nfa& n, const StateSet& s) {
    StateSet closure = s;
    std::queue<std::string> pending;
    for (const std::string& q : s) {
        pending.push(q);
    }
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        for (const std::string& r : delta_of(n, q, EPS)) {
            if (closure.insert(r).second) {
                pending.push(r);
            }
        }
    }
    return closure;
}

Seguir un NFA: el conjunto de estados activos

Listar todos los caminos sirve para entender, pero no para calcular: una cadena de nn símbolos puede tener una cantidad exponencial de caminos. La segunda imagen del no determinismo da un método mejor. No interesa cuántas copias de la máquina hay, sino en qué estados hay alguna. Llamamos estados activos a esos estados. Antes de leer nada, los estados activos son el inicial y todo lo que se alcanza desde él con transiciones ε\varepsilon. Cada símbolo transforma el conjunto de estados activos en otro.

Definición. La función de transición extendida de un NFA trabaja sobre conjuntos de estados. Para S⊆QS \subseteq Q:

δ∗(S,ε)=E(S)δ∗(S,xa)=E( ⋃q∈δ∗(S,x)δ(q,a))para toda cadena x y todo sıˊmbolo a\begin{aligned} \delta^*(S, \varepsilon) &= E(S) \\ \delta^*(S, xa) &= E\Bigl(\,\bigcup_{q \in \delta^*(S, x)} \delta(q, a)\Bigr) && \text{para toda cadena } x \text{ y todo símbolo } a \end{aligned}

La segunda línea se lee en tres pasos: se toman los estados activos después de xx; desde cada uno se siguen todas las flechas con aa y se juntan los destinos; y se cierra el resultado con las transiciones ε\varepsilon. El conjunto de estados activos después de leer ww es δ∗({q0},w)\delta^*(\{q_0\}, w).

Hagámoslo a mano con el autómata de Contiene 101 o 11 y w=01011w = \mathtt{01011}. En cada fila, la tercera columna junta los destinos de las flechas con el símbolo leído, y la cuarta le aplica la clausura.

Leído Símbolo Destinos de las flechas Estados activos
ε\varepsilon E({q0})={q0}E(\{q_0\}) = \{q_0\}
0\mathtt{0} 0\mathtt{0} δ(q0,0)={q0}\delta(q_0, \mathtt{0}) = \{q_0\} {q0}\{q_0\}
01\mathtt{01} 1\mathtt{1} δ(q0,1)={q0,q1}\delta(q_0, \mathtt{1}) = \{q_0, q_1\} {q0,q1,q2}\{q_0, q_1, q_2\}
010\mathtt{010} 0\mathtt{0} {q0}∪{q2}∪∅={q0,q2}\{q_0\} \cup \{q_2\} \cup \emptyset = \{q_0, q_2\} {q0,q2}\{q_0, q_2\}
0101\mathtt{0101} 1\mathtt{1} {q0,q1}∪{q3}={q0,q1,q3}\{q_0, q_1\} \cup \{q_3\} = \{q_0, q_1, q_3\} {q0,q1,q2,q3}\{q_0, q_1, q_2, q_3\}
01011\mathtt{01011} 1\mathtt{1} {q0,q1}∪∅∪{q3}∪{q3}={q0,q1,q3}\{q_0, q_1\} \cup \emptyset \cup \{q_3\} \cup \{q_3\} = \{q_0, q_1, q_3\} {q0,q1,q2,q3}\{q_0, q_1, q_2, q_3\}
Animación del NFA de Contiene 101 o 11 con la cadena 01011. Arriba está la cadena, con una marca que avanza un símbolo por paso; en el medio, el diagrama, con todos los estados activos resaltados a la vez; abajo se va escribiendo la secuencia de conjuntos. En cada paso, una ficha recorre cada flecha que se sigue con el símbolo leído, y después otra recorre la flecha ε cuando la clausura agrega un estado. Antes de leer nada, el único estado activo es q₀. Lee 0: q₀ vuelve a q₀, y los activos son {q₀}. Lee 1: de q₀ se va a q₀ y a q₁, y la clausura agrega q₂: {q₀, q₁, q₂}. Lee 0: q₀ se queda, q₁ pasa a q₂ y la copia que estaba en q₂ muere: {q₀, q₂}. Lee 1: q₀ da q₀ y q₁, q₂ da q₃, y la clausura agrega q₂: {q₀, q₁, q₂, q₃}. Lee 1: de q₁ no sale flecha con 1, los demás dan q₀, q₁ y q₃, y la clausura agrega q₂: otra vez {q₀, q₁, q₂, q₃}. Termina con q₃ activo, que está en F, y aceptaAnimación del NFA de Contiene 101 o 11 con la cadena 01011. Arriba está la cadena, con una marca que avanza un símbolo por paso; en el medio, el diagrama, con todos los estados activos resaltados a la vez; abajo se va escribiendo la secuencia de conjuntos. En cada paso, una ficha recorre cada flecha que se sigue con el símbolo leído, y después otra recorre la flecha ε cuando la clausura agrega un estado. Antes de leer nada, el único estado activo es q₀. Lee 0: q₀ vuelve a q₀, y los activos son {q₀}. Lee 1: de q₀ se va a q₀ y a q₁, y la clausura agrega q₂: {q₀, q₁, q₂}. Lee 0: q₀ se queda, q₁ pasa a q₂ y la copia que estaba en q₂ muere: {q₀, q₂}. Lee 1: q₀ da q₀ y q₁, q₂ da q₃, y la clausura agrega q₂: {q₀, q₁, q₂, q₃}. Lee 1: de q₁ no sale flecha con 1, los demás dan q₀, q₁ y q₃, y la clausura agrega q₂: otra vez {q₀, q₁, q₂, q₃}. Termina con q₃ activo, que está en F, y acepta
La tabla, en movimiento. No se sigue un camino: se sigue el conjunto de estados donde hay alguna copia.

En la tercera fila, la clausura agrega q2q_2 porque q1q_1 entró al conjunto y q2∈E({q1})q_2 \in E(\{q_1\}). En la cuarta, los tres estados activos aportan δ(q0,0)={q0}\delta(q_0, \mathtt{0}) = \{q_0\}, δ(q1,0)={q2}\delta(q_1, \mathtt{0}) = \{q_2\} y δ(q2,0)=∅\delta(q_2, \mathtt{0}) = \emptyset: la copia que estaba en q2q_2 murió, y no se nota porque el conjunto simplemente no recibe nada de ella. Al final, q3q_3 está activo y es de aceptación. El programa run_nfa hace la misma cuenta:

$ build/run_nfa machines/contains_101_or_11.nfa 01011 0100
w = 01011
  {q0} -0-> {q0} -1-> {q0,q1,q2} -0-> {q0,q2} -1-> {q0,q1,q2,q3} -1-> {q0,q1,q2,q3}
  termina con {q0,q1,q2,q3} activos, y q3 está en F: acepta
w = 0100
  {q0} -0-> {q0} -1-> {q0,q1,q2} -0-> {q0,q2} -0-> {q0}
  termina con {q0} activos, y ninguno está en F: rechaza

Con 0100\mathtt{0100}, el conjunto se achica al final: la copia de q2q_2 esperaba un 1\mathtt{1} y llegó un 0\mathtt{0}. Queda solo q0q_0, que no es de aceptación. El conjunto de estados activos puede incluso quedar vacío, cuando mueren todas las copias:

$ build/run_nfa machines/abc_blocks.nfa aacc abca ''
w = aacc
  {qa,qb,qc} -a-> {qa,qb,qc} -a-> {qa,qb,qc} -c-> {qc} -c-> {qc}
  termina con {qc} activos, y qc está en F: acepta
w = abca
  {qa,qb,qc} -a-> {qa,qb,qc} -b-> {qb,qc} -c-> {qc} -a-> {}
  termina con {} activos, y ninguno está en F: rechaza
w = ε
  {qa,qb,qc}
  termina con {qa,qb,qc} activos, y qc está en F: acepta

Con abca\mathtt{abca}, después de la c\mathtt{c} solo queda qcq_c, que no tiene flecha con a\mathtt{a}: el conjunto pasa a ser ∅\emptyset. Desde ∅\emptyset ya no se sale, porque no hay ningún estado del que seguir flechas. Y con la cadena vacía se ve para qué sirve la primera línea de la definición: los estados activos antes de leer nada son E({qa})E(\{q_a\}), que ya contiene a qcq_c.

Lo que hace que este método sea correcto es que el conjunto calculado coincide con la definición por caminos.

Lema (de los estados activos). Para todo conjunto S⊆QS \subseteq Q y toda cadena ww, δ∗(S,w)\delta^*(S, w) es exactamente el conjunto de los estados rr para los que hay un camino con etiqueta ww desde algún estado de SS hasta rr.

La demostración es por inducción sobre ∣w∣|w| y está en la sesión B, en Por qué funciona: la equivalencia, porque es la mitad del teorema principal de la semana. Por ahora tomemos su consecuencia.

Corolario. NN acepta ww si y solo si δ∗({q0},w)∩F≠∅\delta^*(\{q_0\}, w) \cap F \neq \emptyset: algún estado activo al final es de aceptación.

En efecto, por definición NN acepta ww si hay un camino con etiqueta ww de q0q_0 a algún r∈Fr \in F, y por el lema esos rr son los elementos de δ∗({q0},w)\delta^*(\{q_0\}, w) que están en FF.

En C++. Un paso con el símbolo a y la función extendida, en nfa.h. Son las dos líneas de la definición.

inline StateSet step(const Nfa& n, const StateSet& s, char a) {
    StateSet targets;
    for (const std::string& q : s) {
        StateSet next = delta_of(n, q, a);
        targets.insert(next.begin(), next.end());
    }
    return eps_closure(n, targets);
}

inline StateSet delta_star(const Nfa& n, const StateSet& s, const std::string& w) {
    StateSet active = eps_closure(n, s);
    for (char a : w) {
        active = step(n, active, a);
    }
    return active;
}

inline bool accepts(const Nfa& n, const std::string& w) {
    return has_accept(n, delta_star(n, {n.start}, w));
}

test_nfa compara esta simulación con una función que busca un camino directamente, siguiendo la definición, en 200 NFA generados al azar con transiciones ε\varepsilon y ciclos: coinciden en todas las cadenas probadas.

¿Cuánto cuesta simular un NFA así? Si la máquina tiene nn estados, el conjunto de estados activos tiene a lo sumo nn elementos. Para cada símbolo de la entrada se recorren los estados activos, a lo sumo nn, y de cada uno se juntan sus destinos, a lo sumo nn. Con las clausuras calculadas de antemano, cada símbolo cuesta del orden de n2n^2 operaciones, y la cadena completa ∣w∣⋅n2|w| \cdot n^2. Es más que el paso único de un DFA, pero no es exponencial: aunque haya una cantidad exponencial de caminos, hay a lo sumo nn estados donde pueden estar.

Idea clave. Para simular un NFA no se siguen los caminos: se sigue el conjunto de estados activos. Se empieza con E({q0})E(\{q_0\}). Con cada símbolo, se siguen todas las flechas con ese símbolo desde todos los estados activos y se cierra con las transiciones ε\varepsilon. Se acepta si al final hay algún estado de aceptación activo.

En la práctica. Hay dos familias de programas que buscan patrones en texto. Unos prueban un camino a la vez y retroceden cuando falla, con backtracking: es lo que hacen los motores de expresiones regulares de muchos lenguajes, y con ciertos patrones y ciertas entradas tardan un tiempo exponencial. Otros llevan el conjunto de estados activos, como run_nfa, y su tiempo crece en proporción a la longitud del texto: es el enfoque de grep y de bibliotecas como RE2. La diferencia entre las dos familias es la diferencia entre la tercera imagen del no determinismo, el árbol, y la segunda. En la semana 3 veremos cómo se pasa de una expresión regular a un NFA, y el laboratorio será un grep pequeño que simula así.

Todo DFA es un NFA

Un DFA es el caso particular de un NFA en el que nunca hay que elegir. Con precisión: si M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) es un DFA, el NFA N=(Q,Σ,δ′,q0,F)N = (Q, \Sigma, \delta', q_0, F) con

δ′(q,a)={δ(q,a)}para a∈Σ,δ′(q,ε)=∅\delta'(q, a) = \{\delta(q, a)\} \quad \text{para } a \in \Sigma, \qquad \delta'(q, \varepsilon) = \emptyset

tiene, para cada cadena, un solo camino desde q0q_0, que es la ejecución de MM. Luego L(N)=L(M)L(N) = L(M). En los archivos ni siquiera hay que convertir nada: todo archivo .dfa es un archivo .nfa válido, en el que cada línea tiene un solo destino y no falta ninguna.

$ build/run_nfa machines/ends_01.dfa 0101
w = 0101
  {q0} -0-> {q1} -1-> {q2} -0-> {q1} -1-> {q2}
  termina con {q2} activos, y q2 está en F: acepta

El conjunto de estados activos de un DFA tiene siempre un solo estado.

Entonces todo lenguaje regular es reconocido por algún NFA. La pregunta interesante es la contraria. Los NFA parecen más capaces: adivinan, se saltan símbolos, resuelven en 4 estados lo que al DFA le cuesta 8.

¿Hay algún lenguaje que un NFA reconozca y que ningún DFA pueda reconocer?

Piensen qué responderían antes de seguir. La segunda imagen del no determinismo ya contiene la respuesta: lo único que hace falta para simular un NFA es el conjunto de estados activos, y un NFA con nn estados tiene una cantidad finita de conjuntos de estados.

La construcción de subconjuntos

Miren otra vez la salida de run_nfa. Es una secuencia de conjuntos unidos por flechas con símbolos, un conjunto después de cada símbolo, y el siguiente depende solo del conjunto actual y del símbolo leído. Eso es la ejecución de una máquina determinista cuyos estados son conjuntos.

Idea clave. El conjunto de estados activos de un NFA es un solo estado de un DFA. Como un NFA con nn estados tiene 2n2^n subconjuntos de estados, y 2n2^n es finito, ese DFA existe.

Es la misma jugada que el producto de la semana pasada. Ahí, para correr dos máquinas a la vez, el estado nuevo era un par de estados. Aquí, para correr todas las copias de una máquina a la vez, el estado nuevo es un conjunto de estados.

Un primer ejemplo

El lenguaje Termina en 01 tiene un NFA de tres estados que adivina dónde empieza el 01\mathtt{01} final:

$ build/show_nfa machines/ends_01.nfa
Q  = {q0, q1, q2}
Σ  = {0, 1}
q0 = q0
F  = {q2}

     δ   0        1     ε
->   q0  {q0,q1}  {q0}  {}
     q1  {}       {q2}  {}
   * q2  {}       {}    {}

no tiene transiciones ε: E(S) = S para todo conjunto S

Construyamos el DFA a mano. Su estado inicial es el conjunto de estados activos antes de leer nada: E({q0})={q0}E(\{q_0\}) = \{q_0\}. Desde cada conjunto que vaya apareciendo, calculamos a qué conjunto se pasa con cada símbolo, igual que en la tabla de la sección Seguir un NFA: el conjunto de estados activos.

  • Desde {q0}\{q_0\}: con 0\mathtt{0}, δ(q0,0)={q0,q1}\delta(q_0, \mathtt{0}) = \{q_0, q_1\}, un conjunto nuevo. Con 1\mathtt{1}, δ(q0,1)={q0}\delta(q_0, \mathtt{1}) = \{q_0\}, que ya teníamos.
  • Desde {q0,q1}\{q_0, q_1\}: con 0\mathtt{0}, {q0,q1}∪∅={q0,q1}\{q_0, q_1\} \cup \emptyset = \{q_0, q_1\}. Con 1\mathtt{1}, {q0}∪{q2}={q0,q2}\{q_0\} \cup \{q_2\} = \{q_0, q_2\}, nuevo.
  • Desde {q0,q2}\{q_0, q_2\}: con 0\mathtt{0}, {q0,q1}∪∅={q0,q1}\{q_0, q_1\} \cup \emptyset = \{q_0, q_1\}. Con 1\mathtt{1}, {q0}∪∅={q0}\{q_0\} \cup \emptyset = \{q_0\}.

No apareció ningún conjunto más: el DFA tiene tres estados. De ellos, el único que contiene a q2q_2, el estado de aceptación del NFA, es {q0,q2}\{q_0, q_2\}. El programa subset hace esta cuenta y la muestra como tabla, con una fila por cada conjunto en el orden en que aparecieron:

$ build/subset machines/ends_01.nfa
E({q0}) = {q0}

     S        0        1
->   {q0}     {q0,q1}  {q0}
     {q0,q1}  {q0,q1}  {q0,q2}
   * {q0,q2}  {q0,q1}  {q0}

el NFA tiene 3 estados: 2^3 = 8 subconjuntos, 3 alcanzables
Animación de la construcción de subconjuntos sobre el NFA de Termina en 01. A la izquierda están el NFA, con estados q₀, q₁ y q₂, y la tabla que se va llenando; a la derecha, el DFA, que crece un estado por vez. En cada paso se resalta el conjunto que se procesa, en el DFA y como estados activos del NFA, y se dibuja una flecha por cada símbolo. Primero aparece el estado inicial, {q₀}. Desde {q₀}: con 0 sale una flecha a un estado nuevo, {q₀, q₁}; con 1, un bucle en {q₀}. Desde {q₀, q₁}: con 0, un bucle; con 1, una flecha a un estado nuevo, {q₀, q₂}, que tiene doble círculo. Desde {q₀, q₂}: con 0, una flecha a {q₀, q₁}; con 1, una flecha a {q₀}. No aparece ningún conjunto nuevo y la construcción termina con 3 de los 8 subconjuntosAnimación de la construcción de subconjuntos sobre el NFA de Termina en 01. A la izquierda están el NFA, con estados q₀, q₁ y q₂, y la tabla que se va llenando; a la derecha, el DFA, que crece un estado por vez. En cada paso se resalta el conjunto que se procesa, en el DFA y como estados activos del NFA, y se dibuja una flecha por cada símbolo. Primero aparece el estado inicial, {q₀}. Desde {q₀}: con 0 sale una flecha a un estado nuevo, {q₀, q₁}; con 1, un bucle en {q₀}. Desde {q₀, q₁}: con 0, un bucle; con 1, una flecha a un estado nuevo, {q₀, q₂}, que tiene doble círculo. Desde {q₀, q₂}: con 0, una flecha a {q₀, q₁}; con 1, una flecha a {q₀}. No aparece ningún conjunto nuevo y la construcción termina con 3 de los 8 subconjuntos
El DFA se arma generando solo los subconjuntos que aparecen. Cada fila de la tabla es un estado con sus dos flechas.

Comparen con el DFA de machines/ends_01.dfa, el que diseñamos la semana pasada pensando qué recordar. Es la misma máquina, con {q0}\{q_0\} en el lugar de q0q_0, {q0,q1}\{q_0, q_1\} en el de q1q_1 y {q0,q2}\{q_0, q_2\} en el de q2q_2. La construcción encontró sola el diseño: “termina en 0\mathtt{0}” es “la copia que apostó por ese 0\mathtt{0} sigue viva”.

La construcción

Construcción (de subconjuntos). Sea N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F) un NFA. Se define el DFA D=(QD,Σ,δD,qD,FD)D = (Q_D, \Sigma, \delta_D, q_D, F_D) con:

  • QD=P(Q)Q_D = \mathcal{P}(Q): un estado por cada subconjunto de QQ.
  • qD=E({q0})q_D = E(\{q_0\}): los estados activos antes de leer nada.
  • Para S∈QDS \in Q_D y a∈Σa \in \Sigma:
δD(S,a)=E( ⋃q∈Sδ(q,a))\delta_D(S, a) = E\Bigl(\,\bigcup_{q \in S} \delta(q, a)\Bigr)
  • FD={ S∈QD:S∩F≠∅ }F_D = \{\, S \in Q_D : S \cap F \neq \emptyset \,\}: los subconjuntos que contienen algún estado de aceptación de NN.

Es un DFA de verdad. QDQ_D es finito, con 2∣Q∣2^{|Q|} elementos. Y δD\delta_D está definida para todo subconjunto y todo símbolo, y da un solo subconjunto: es una función total de QD×ΣQ_D \times \Sigma en QDQ_D. En este DFA no hay transiciones ε\varepsilon ni elecciones: todo eso quedó absorbido dentro de la definición de δD\delta_D.

Cada pieza de la construcción copia una pieza de la simulación con estados activos. El estado inicial es la primera línea de la definición de δ∗\delta^*. La transición es la segunda línea. Y FDF_D es el corolario del lema: se acepta si algún estado activo es de aceptación.

Error común. Tomar como estados de aceptación del DFA los subconjuntos formados solo por estados de FF, o exigir que el subconjunto sea igual a FF. La condición es S∩F≠∅S \cap F \neq \emptyset: basta con que una copia esté en un estado de aceptación, porque el NFA acepta cuando algún camino acepta. En el ejemplo, {q0,q2}\{q_0, q_2\} es de aceptación aunque q0q_0 no lo sea.

El conjunto vacío también es un estado de QDQ_D, y tiene un papel conocido. Como no tiene elementos, δD(∅,a)=E(∅)=∅\delta_D(\emptyset, a) = E(\emptyset) = \emptyset para todo símbolo: de ∅\emptyset no se sale. Y ∅∩F=∅\emptyset \cap F = \emptyset: no es de aceptación. Es el estado trampa. En un NFA los caminos que mueren no necesitan un estado; en el DFA, “ya murieron todos” es el estado ∅\emptyset.

Solo los subconjuntos alcanzables

La definición usa los 2n2^n subconjuntos, pero la mayoría no aparece nunca. En el primer ejemplo había 8 y se usaron 3. La semana pasada vimos que los estados inalcanzables de un DFA se pueden borrar sin cambiar su lenguaje, porque ninguna ejecución pasa por ellos. Entonces conviene no generarlos: se parte del estado inicial y se agregan solo los subconjuntos que van apareciendo, como hicimos a mano.

algoritmo subconjuntos(N)
    inicial ← E({q0})
    estados ← {inicial}
    cola ← [inicial]
    mientras cola no esté vacía
        S ← sacar el primero de cola
        para cada símbolo a de Σ
            T ← E(unión de δ(q, a) para cada q en S)
            δD(S, a) ← T
            si T no está en estados entonces
                agregar T a estados
                poner T al final de cola
            fin si
        fin para
    fin mientras
    FD ← los S de estados que contienen algún estado de F
    devolver (estados, Σ, δD, inicial, FD)
fin algoritmo

Es un recorrido en anchura de un grafo que no está escrito en ninguna parte: sus vértices son los subconjuntos, y los vecinos de cada uno se calculan cuando se lo visita. Termina porque cada subconjunto entra en la cola a lo sumo una vez y hay una cantidad finita de ellos.

Con el autómata de la sesión A, el tercer símbolo desde el final es 1:

$ build/subset machines/third_from_end.nfa
E({q0}) = {q0}

     S              0              1
->   {q0}           {q0}           {q0,q1}
     {q0,q1}        {q0,q2}        {q0,q1,q2}
     {q0,q2}        {q0,q3}        {q0,q1,q3}
     {q0,q1,q2}     {q0,q2,q3}     {q0,q1,q2,q3}
   * {q0,q3}        {q0}           {q0,q1}
   * {q0,q1,q3}     {q0,q2}        {q0,q1,q2}
   * {q0,q2,q3}     {q0,q3}        {q0,q1,q3}
   * {q0,q1,q2,q3}  {q0,q2,q3}     {q0,q1,q2,q3}

el NFA tiene 4 estados: 2^4 = 16 subconjuntos, 8 alcanzables

Salieron 8 estados: los que anunciamos al principio del capítulo para el DFA que recuerda los tres últimos símbolos. Y son eso mismo. Todos los subconjuntos alcanzables contienen a q0q_0, porque la copia que nunca apuesta sigue siempre viva. Los otros tres estados dicen cuáles de los tres últimos símbolos fueron 1\mathtt{1}: q1q_1 está activo si el último símbolo fue 1\mathtt{1}, q2q_2 si lo fue el penúltimo, y q3q_3 si lo fue el antepenúltimo. El subconjunto {q0,q1,q3}\{q_0, q_1, q_3\} es “los tres últimos símbolos fueron 101\mathtt{101}”. Los cuatro estados de aceptación son los que tienen a q3q_3.

Una lectura de la fila de {q0,q1}\{q_0, q_1\} con 0\mathtt{0}, para fijar la cuenta: δ(q0,0)={q0}\delta(q_0, \mathtt{0}) = \{q_0\} y δ(q1,0)={q2}\delta(q_1, \mathtt{0}) = \{q_2\}, y la unión es {q0,q2}\{q_0, q_2\}. No hay transiciones ε\varepsilon, así que la clausura no agrega nada.

El programa nfa_to_dfa escribe el resultado como archivo .dfa, con el conjunto como nombre del estado, y lo puede seguir el run_dfa de la semana pasada:

$ build/nfa_to_dfa machines/third_from_end.nfa | build/run_dfa - 0110 100
w = 0110
  {q0} -0-> {q0} -1-> {q0,q1} -1-> {q0,q1,q2} -0-> {q0,q2,q3}
  termina en {q0,q2,q3}, que está en F: acepta
w = 100
  {q0} -1-> {q0,q1} -0-> {q0,q2} -0-> {q0,q3}
  termina en {q0,q3}, que está en F: acepta

La ejecución del DFA con 0110\mathtt{0110} es, conjunto por conjunto, lo que imprime build/run_nfa machines/third_from_end.nfa 0110. La diferencia está en quién hace el trabajo. run_nfa calcula cada conjunto mientras lee la cadena. El DFA los tiene calculados de antemano: mientras lee, solo busca una casilla en su tabla.

Con transiciones ε

Con transiciones ε\varepsilon el algoritmo es el mismo. La clausura aparece en dos lugares: en el estado inicial y al final de cada transición.

$ build/subset machines/contains_101_or_11.nfa
E({q0}) = {q0}

     S              0              1
->   {q0}           {q0}           {q0,q1,q2}
     {q0,q1,q2}     {q0,q2}        {q0,q1,q2,q3}
     {q0,q2}        {q0}           {q0,q1,q2,q3}
   * {q0,q1,q2,q3}  {q0,q2,q3}     {q0,q1,q2,q3}
   * {q0,q2,q3}     {q0,q3}        {q0,q1,q2,q3}
   * {q0,q3}        {q0,q3}        {q0,q1,q2,q3}

el NFA tiene 4 estados: 2^4 = 16 subconjuntos, 6 alcanzables

Desde {q0}\{q_0\} con 1\mathtt{1}, las flechas llevan a {q0,q1}\{q_0, q_1\} y la clausura agrega q2q_2: el subconjunto {q0,q1}\{q_0, q_1\}, sin q2q_2, no aparece nunca en este DFA. Las tres últimas filas son de aceptación y desde ellas solo se llega a ellas: una vez visto el patrón, se acepta termine como termine. Un diseñador las habría juntado en un solo estado “ya ganó”. La construcción no minimiza: da un DFA correcto, y no siempre el más pequeño. De eso se ocupa la semana 4.

En el autómata de los bloques, la clausura actúa ya en el estado inicial, y aparece el conjunto vacío:

$ build/subset machines/abc_blocks.nfa
E({qa}) = {qa,qb,qc}

     S           a           b           c
-> * {qa,qb,qc}  {qa,qb,qc}  {qb,qc}     {qc}
   * {qb,qc}     {}          {qb,qc}     {qc}
   * {qc}        {}          {}          {qc}
     {}          {}          {}          {}

el NFA tiene 3 estados: 2^3 = 8 subconjuntos, 4 alcanzables

El estado inicial del DFA es {qa,qb,qc}\{q_a, q_b, q_c\} y es de aceptación, porque contiene a qcq_c: así queda aceptada la cadena vacía. La última fila es el estado trampa ∅\emptyset, al que se cae con la primera letra fuera de orden.

Error común. Olvidar la clausura ε\varepsilon del estado inicial y empezar en {q0}\{q_0\}. En el autómata de los bloques, el DFA empezaría en {qa}\{q_a\}, que no es de aceptación, y rechazaría la cadena vacía y también b\mathtt{b}: desde {qa}\{q_a\}, las flechas con b\mathtt{b} no llevan a ningún lado. Es el error más frecuente en el laboratorio de esta semana.

En C++. La función subset_construction de nfa.h es el pseudocódigo, con std::set<StateSet> para saber si un subconjunto ya apareció y std::queue<StateSet> para los pendientes. El nombre de cada estado del DFA es el conjunto escrito sin espacios, {q0,q1}, para que quepa en un archivo .dfa.

while (!pending.empty()) {
    StateSet s = pending.front();
    pending.pop();
    std::string name = set_name(n, s);
    if (has_accept(n, s)) {
        d.accept.insert(name);
    }
    for (char a : n.alphabet) {
        StateSet t = step(n, s, a);
        d.delta[{name, a}] = set_name(n, t);
        if (seen.insert(t).second) {
            found.push_back(t);
            d.states.push_back(set_name(n, t));
            pending.push(t);
        }
    }
}

Un conjunto de nombres se lee bien y es lento. En el laboratorio conviene numerar los estados del NFA y guardar cada subconjunto como un entero, con un bit por estado.

Por qué funciona: la equivalencia

Teorema. Para todo NFA NN hay un DFA DD con L(D)=L(N)L(D) = L(N).

Demostración. Por construcción.

Qué se construye: el DFA DD de la construcción de subconjuntos.

Por qué reconoce L(N)L(N): hay que ver que DD acepta una cadena si y solo si NN la acepta. El argumento tiene dos lemas. El primero dice que la función δ∗\delta^* sobre conjuntos calcula lo que la definición por caminos pide. El segundo, que DD hace con sus estados lo mismo que δ∗\delta^* con sus conjuntos. Los dos son por inducción sobre la longitud de la cadena.

Lema (de los estados activos). Para todo S⊆QS \subseteq Q y toda cadena ww:

δ∗(S,w)={ r∈Q:hay un camino con etiqueta w desde alguˊn estado de S hasta r }\delta^*(S, w) = \{\, r \in Q : \text{hay un camino con etiqueta } w \text{ desde algún estado de } S \text{ hasta } r \,\}

Demostración. Por inducción sobre ∣w∣|w|, con SS fijo.

Caso base: w=εw = \varepsilon. Por definición, δ∗(S,ε)=E(S)\delta^*(S, \varepsilon) = E(S), y E(S)E(S) es el conjunto de los estados a los que llega un camino con etiqueta ε\varepsilon desde algún estado de SS. Es lo que afirma el lema.

Paso inductivo: w=xaw = xa, y suponemos el lema para xx. Llamemos A=δ∗(S,x)A = \delta^*(S, x), de modo que δ∗(S,xa)=E(⋃q∈Aδ(q,a))\delta^*(S, xa) = E\bigl(\bigcup_{q \in A} \delta(q, a)\bigr). Hay que demostrar dos inclusiones.

Todo estado de δ∗(S,xa)\delta^*(S, xa) tiene un camino. Sea r∈δ∗(S,xa)r \in \delta^*(S, xa). Por la definición de EE, hay un estado r′r' en ⋃q∈Aδ(q,a)\bigcup_{q \in A} \delta(q, a) y un camino con etiqueta ε\varepsilon de r′r' a rr. Que r′r' esté en la unión quiere decir que r′∈δ(q,a)r' \in \delta(q, a) para algún q∈Aq \in A. Por la hipótesis de inducción, como q∈A=δ∗(S,x)q \in A = \delta^*(S, x), hay un camino con etiqueta xx desde algún p∈Sp \in S hasta qq. Pegando las tres partes, el camino de pp a qq, el paso de qq a r′r' con aa, y el camino ε\varepsilon de r′r' a rr, se obtiene un camino de pp a rr cuya etiqueta es x⋅a⋅ε=xax \cdot a \cdot \varepsilon = xa.

Todo estado con un camino está en δ∗(S,xa)\delta^*(S, xa). Supongamos que hay un camino con etiqueta xaxa desde algún p∈Sp \in S hasta rr, con estados r0,…,rmr_0, \ldots, r_m y etiquetas y1,…,ymy_1, \ldots, y_m. La concatenación de las etiquetas es xaxa, que termina en el símbolo aa. Sea jj la posición de la última etiqueta que no es ε\varepsilon. Entonces yj=ay_j = a; las etiquetas anteriores forman xx, es decir, y1⋯yj−1=xy_1 \cdots y_{j-1} = x; y las posteriores, yj+1,…,ymy_{j+1}, \ldots, y_m, son todas ε\varepsilon. El camino se parte en tres:

  • De r0=pr_0 = p a rj−1r_{j-1}, con etiqueta xx. Por la hipótesis de inducción, rj−1∈δ∗(S,x)=Ar_{j-1} \in \delta^*(S, x) = A.
  • El paso de rj−1r_{j-1} a rjr_j con aa: rj∈δ(rj−1,a)r_j \in \delta(r_{j-1}, a), así que rjr_j está en ⋃q∈Aδ(q,a)\bigcup_{q \in A} \delta(q, a).
  • De rjr_j a rm=rr_m = r, con etiqueta ε\varepsilon: rr está en la clausura de cualquier conjunto que contenga a rjr_j.

Luego r∈E(⋃q∈Aδ(q,a))=δ∗(S,xa)r \in E\bigl(\bigcup_{q \in A} \delta(q, a)\bigr) = \delta^*(S, xa). ∎

Lema (de la construcción). Para toda cadena ww: δD∗(qD,w)=δ∗({q0},w)\delta_D^*(q_D, w) = \delta^*(\{q_0\}, w).

A la izquierda está la función extendida del DFA DD, la de la semana pasada, que devuelve un estado de DD. A la derecha, la función extendida del NFA NN sobre conjuntos. El lema dice que el estado en el que queda DD después de leer ww es el conjunto de estados activos de NN después de leer ww.

Demostración. Por inducción sobre ∣w∣|w|.

Caso base: w=εw = \varepsilon. Por la definición de la función extendida de un DFA, δD∗(qD,ε)=qD\delta_D^*(q_D, \varepsilon) = q_D, y qD=E({q0})q_D = E(\{q_0\}) por construcción. Por la definición de la función extendida del NFA, δ∗({q0},ε)=E({q0})\delta^*(\{q_0\}, \varepsilon) = E(\{q_0\}). Coinciden.

Paso inductivo: w=xaw = xa, y suponemos el lema para xx.

δD∗(qD,xa)=δD(δD∗(qD,x),a)definicioˊn de δD∗=δD(δ∗({q0},x),a)hipoˊtesis de induccioˊn=E( ⋃q∈δ∗({q0},x)δ(q,a))definicioˊn de δD=δ∗({q0},xa)definicioˊn de δ∗ en el NFA\begin{aligned} \delta_D^*(q_D, xa) &= \delta_D(\delta_D^*(q_D, x), a) && \text{definición de } \delta_D^* \\ &= \delta_D(\delta^*(\{q_0\}, x), a) && \text{hipótesis de inducción} \\ &= E\Bigl(\,\bigcup_{q \in \delta^*(\{q_0\}, x)} \delta(q, a)\Bigr) && \text{definición de } \delta_D \\ &= \delta^*(\{q_0\}, xa) && \text{definición de } \delta^* \text{ en el NFA} \end{aligned}

∎

Con los dos lemas, el teorema es una cadena de equivalencias. Para toda cadena ww:

D acepta w  ⟺  δD∗(qD,w)∈FDdefinicioˊn de aceptar en un DFA  ⟺  δD∗(qD,w)∩F≠∅definicioˊn de FD  ⟺  δ∗({q0},w)∩F≠∅lema de la construccioˊn  ⟺  hay un camino con etiqueta w de q0 a un estado de Flema de los estados activos  ⟺  N acepta wdefinicioˊn de aceptar en un NFA\begin{aligned} D \text{ acepta } w &\iff \delta_D^*(q_D, w) \in F_D && \text{definición de aceptar en un DFA} \\ &\iff \delta_D^*(q_D, w) \cap F \neq \emptyset && \text{definición de } F_D \\ &\iff \delta^*(\{q_0\}, w) \cap F \neq \emptyset && \text{lema de la construcción} \\ &\iff \text{hay un camino con etiqueta } w \text{ de } q_0 \text{ a un estado de } F && \text{lema de los estados activos} \\ &\iff N \text{ acepta } w && \text{definición de aceptar en un NFA} \end{aligned}

Cada línea es un “si y solo si”, así que valen las dos direcciones: L(D)=L(N)L(D) = L(N). ∎

El lema de la construcción es casi inmediato, porque δD\delta_D se definió copiando la segunda línea de δ∗\delta^*. El trabajo de verdad está en el lema de los estados activos, que es donde se pasa de “existe un camino” a un cálculo con conjuntos. El DFA con solo los estados alcanzables, que es el que construyen los programas, reconoce el mismo lenguaje que DD: se le quitaron estados por los que no pasa ninguna ejecución.

Corolario. Un lenguaje es regular si y solo si algún NFA lo reconoce.

Demostración. Si AA es regular, lo reconoce un DFA, y todo DFA es un NFA. Si a AA lo reconoce un NFA, por el teorema lo reconoce un DFA, y entonces es regular por definición. ∎

Esta es la respuesta a la pregunta de la sesión A: no, los NFA no reconocen nada más. Y el corolario cambia la manera de trabajar. Desde ahora, para demostrar que un lenguaje es regular basta dar un NFA, que casi siempre es más fácil de diseñar y de justificar. El resto del capítulo lo aprovecha.

test_subset comprueba los dos lemas con programas. Para cada autómata del capítulo y para 200 NFA al azar, recorre todas las cadenas hasta cierta longitud y verifica que el estado en el que queda el DFA es el nombre del conjunto de estados activos del NFA, y que los dos aceptan lo mismo.

En la práctica. Los generadores de analizadores léxicos, como lex y flex, reciben las expresiones regulares de los tokens de un lenguaje, arman un NFA y lo convierten en un DFA con esta construcción antes de compilar: el analizador que resulta solo sigue una tabla. Las herramientas de búsqueda, que reciben un patrón distinto cada vez, suelen construir el DFA mientras leen: calculan un subconjunto la primera vez que lo necesitan y lo guardan por si vuelve a aparecer. Así solo pagan por los subconjuntos que el texto hace aparecer.

El costo: hasta 2ⁿ estados

La construcción de subconjuntos convierte un NFA de nn estados en un DFA de a lo sumo 2n2^n. En los ejemplos salieron muchos menos: 3 de 8, 8 de 16, 6 de 16, 4 de 8. ¿Es el 2n2^n una exageración de la definición, o hay lenguajes en los que de verdad hace falta?

Generalicemos el primer ejemplo. Para cada k≥1k \geq 1, sea

Lk={ w∈{0,1}∗:el k-eˊsimo sıˊmbolo de w desde el final es 1 }L_k = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : \text{el } k\text{-ésimo símbolo de } w \text{ desde el final es } \mathtt{1} \,\}

El NFA es el de siempre con una cadena más larga: q0q_0 espera y apuesta en algún 1\mathtt{1}, y de q1q_1 a qkq_k se avanza con cualquier símbolo. Tiene k+1k + 1 estados. El programa kth_nfa lo escribe para cualquier kk, y kth_table le aplica la construcción de subconjuntos para kk de 1 a 12 y cuenta:

$ build/kth_table
 k   estados del NFA   subconjuntos posibles   estados del DFA (alcanzables)
 1                 2                       4                               2
 2                 3                       8                               4
 3                 4                      16                               8
 4                 5                      32                              16
 5                 6                      64                              32
 6                 7                     128                              64
 7                 8                     256                             128
 8                 9                     512                             256
 9                10                    1024                             512
10                11                    2048                            1024
11                12                    4096                            2048
12                13                    8192                            4096

El NFA crece de uno en uno y el DFA se duplica cada vez: 2k2^k estados. Se alcanzan la mitad de los subconjuntos posibles, y se entiende por qué con lo que vimos para k=3k = 3. Todo subconjunto alcanzable contiene a q0q_0. Y qiq_i está activo exactamente cuando el ii-ésimo símbolo desde el final de lo leído es 1\mathtt{1}, así que la parte del subconjunto que está en {q1,…,qk}\{q_1, \ldots, q_k\} es una foto de los últimos kk símbolos. Hay 2k2^k fotos posibles y todas aparecen.

Eso explica por qué esta construcción da 2k2^k estados. Queda la pregunta de si otro diseño, más astuto, podría hacerlo con menos. La respuesta es que no: todo DFA que reconoce LkL_k tiene al menos 2k2^k estados.

La intuición es la del principio del capítulo. Un DFA no sabe cuándo se va a acabar la cadena, así que tiene que recordar los últimos kk símbolos completos: cualquiera de ellos puede terminar siendo el kk-ésimo desde el final. Si tuviera menos de 2k2^k estados, habría dos cadenas distintas de longitud kk, digamos xx e yy, que lo dejan en el mismo estado, igual que en el argumento de la semana pasada sobre 0n1n\mathtt{0}^n\mathtt{1}^n. Como xx e yy son distintas, difieren en alguna posición, y agregando símbolos al final se puede hacer que justo esa posición sea la kk-ésima desde el final. Con la continuación agregada, una de las dos cadenas está en LkL_k y la otra no, pero la máquina, que estaba en el mismo estado, termina en el mismo estado con las dos. No puede responder bien en ambas.

Esto es la idea, sin los detalles. La demostración completa necesita decir con precisión qué significa que dos cadenas “tengan que” llevar a estados distintos, y esa es la herramienta de la semana 4, el teorema de Myhill-Nerode: ahí se demuestra la cota de 2k2^k y se ve que el DFA de la tabla es el más pequeño posible.

Idea clave. Quitar el no determinismo no cuesta poder de cómputo, pero puede costar tamaño: hay lenguajes con un NFA de k+1k + 1 estados cuyo DFA más pequeño tiene 2k2^k. El NFA es la descripción corta. El DFA es la que se ejecuta rápido.

Hay entonces dos maneras de usar un NFA en un programa, y ninguna es siempre la mejor.

Simular el NFA Convertir a DFA y simular
Trabajo antes de leer Ninguno Hasta 2n2^n estados que construir
Trabajo por símbolo Del orden de n2n^2 Una búsqueda en la tabla
Memoria El NFA y un conjunto La tabla completa del DFA

Si el patrón se usa una vez sobre un texto corto, conviene simular. Si se usa millones de veces, como el analizador léxico de un compilador, conviene pagar la conversión una sola vez.

Cierre bajo unión

La semana pasada demostramos con el producto que los lenguajes regulares son cerrados bajo unión. Con NFA hay otra demostración, más simple, que además sirve de modelo para las dos operaciones que faltan. La idea es que la máquina adivine cuál de los dos autómatas va a aceptar, y corra ese.

Teorema. Si A1A_1 y A2A_2 son lenguajes regulares sobre Σ\Sigma, entonces A1∪A2A_1 \cup A_2 es regular.

Demostración. Por construcción. Sean N1=(Q1,Σ,δ1,q1,F1)N_1 = (Q_1, \Sigma, \delta_1, q_1, F_1) y N2=(Q2,Σ,δ2,q2,F2)N_2 = (Q_2, \Sigma, \delta_2, q_2, F_2) dos NFA con L(N1)=A1L(N_1) = A_1 y L(N2)=A2L(N_2) = A_2. Existen porque todo lenguaje regular tiene un DFA, y un DFA es un NFA. Suponemos que Q1Q_1 y Q2Q_2 no tienen estados en común: si los tienen, se les cambia el nombre.

Qué se construye: el NFA N=(Q,Σ,δ,s,F)N = (Q, \Sigma, \delta, s, F), donde ss es un estado nuevo, que no está en Q1Q_1 ni en Q2Q_2, y:

  • Q={s}∪Q1∪Q2Q = \{s\} \cup Q_1 \cup Q_2.
  • El estado inicial es ss.
  • F=F1∪F2F = F_1 \cup F_2.
  • δ(s,ε)={q1,q2}\delta(s, \varepsilon) = \{q_1, q_2\} y δ(s,a)=∅\delta(s, a) = \emptyset para todo símbolo aa. En los demás estados no cambia nada: δ(q,y)=δ1(q,y)\delta(q, y) = \delta_1(q, y) si q∈Q1q \in Q_1 y δ(q,y)=δ2(q,y)\delta(q, y) = \delta_2(q, y) si q∈Q2q \in Q_2.
Esquema de la construcción. A la izquierda, un estado nuevo s, con la flecha de inicio. A la derecha, dos recuadros, uno encima del otro: N₁, con su estado inicial q₁ a la izquierda y sus estados de aceptación a la derecha, y N₂, con q₂ y los suyos. De s salen dos flechas ε punteadas, una hacia q₁ y otra hacia q₂. El estado s y sus dos flechas, que son lo único nuevo, están en granate. Los estados de aceptación son los de las dos máquinasEsquema de la construcción. A la izquierda, un estado nuevo s, con la flecha de inicio. A la derecha, dos recuadros, uno encima del otro: N₁, con su estado inicial q₁ a la izquierda y sus estados de aceptación a la derecha, y N₂, con q₂ y los suyos. De s salen dos flechas ε punteadas, una hacia q₁ y otra hacia q₂. El estado s y sus dos flechas, que son lo único nuevo, están en granate. Los estados de aceptación son los de las dos máquinas
La unión con un NFA: un estado inicial nuevo que salta, sin leer nada, al inicio de una de las dos máquinas.

Por qué reconoce A1∪A2A_1 \cup A_2: en las dos direcciones.

Si w∈A1∪A2w \in A_1 \cup A_2, digamos w∈A1w \in A_1, entonces hay un camino en N1N_1 de q1q_1 a un estado de F1F_1 con etiqueta ww. Todas sus flechas están también en NN. Poniéndole delante el paso de ss a q1q_1 con ε\varepsilon, queda un camino en NN de ss a un estado de FF con etiqueta εw=w\varepsilon w = w. Luego NN acepta ww. Si w∈A2w \in A_2, lo mismo con N2N_2.

Si NN acepta ww, hay un camino en NN de ss a un estado de FF con etiqueta ww. Como s∉Fs \notin F, el camino tiene al menos un paso, y el primero sale de ss: solo puede ser una de las dos transiciones ε\varepsilon. Digamos que va a q1q_1. Desde un estado de Q1Q_1, las flechas de NN son las de N1N_1 y llevan a estados de Q1Q_1: el resto del camino no sale de N1N_1. Entonces el resto es un camino en N1N_1 de q1q_1 a un estado de F∩Q1=F1F \cap Q_1 = F_1, con etiqueta ww, y w∈A1w \in A_1. Si el primer paso va a q2q_2, sale w∈A2w \in A_2. En los dos casos, w∈A1∪A2w \in A_1 \cup A_2. ∎

El programa combine aplica la construcción a dos archivos. Con los dos DFA de la semana pasada, cantidad par de unos y termina en 01\mathtt{01}:

$ build/combine union machines/even_ones.dfa machines/ends_01.dfa
# Unión de machines/even_ones.dfa y machines/ends_01.dfa.
states: s 1.par 1.impar 2.q0 2.q1 2.q2
alphabet: 0 1
start: s
accept: 1.par 2.q2
delta:
s eps 1.par 2.q0
1.par 0 1.par
1.par 1 1.impar
1.impar 0 1.impar
1.impar 1 1.par
2.q0 0 2.q1
2.q0 1 2.q0
2.q1 0 2.q1
2.q1 1 2.q2
2.q2 0 2.q1
2.q2 1 2.q0

Para que los nombres no choquen, el programa antepone 1. a los estados de la primera máquina y 2. a los de la segunda. Salvo la línea de s, el archivo es la copia de los dos originales.

$ build/combine union machines/even_ones.dfa machines/ends_01.dfa | build/run_nfa - 1101 111
w = 1101
  {s,1.par,2.q0} -1-> {1.impar,2.q0} -1-> {1.par,2.q0} -0-> {1.par,2.q1} -1-> {1.impar,2.q2}
  termina con {1.impar,2.q2} activos, y 2.q2 está en F: acepta
w = 111
  {s,1.par,2.q0} -1-> {1.impar,2.q0} -1-> {1.par,2.q0} -1-> {1.impar,2.q0}
  termina con {1.impar,2.q0} activos, y ninguno está en F: rechaza

Después del primer símbolo, cada conjunto de estados activos tiene un estado de cada máquina. Es el par (p,q)(p, q) del producto de la semana pasada, con otra ropa: comparen con la tabla de la ejecución de 1101\mathtt{1101} en aquel capítulo. Si a este NFA se le aplica la construcción de subconjuntos, salen 7 estados: los 6 pares del producto y el inicial {s,1.par,2.q0}\{s, \mathit{1.par}, \mathit{2.q0}\}, que solo se usa antes de leer nada. test_closure comprueba que este NFA y el producto de la semana pasada aceptan las mismas cadenas.

La comparación de tamaños es la del resto del capítulo. La unión con NFA suma: ∣Q1∣+∣Q2∣+1|Q_1| + |Q_2| + 1 estados. El producto multiplica: ∣Q1∣⋅∣Q2∣|Q_1| \cdot |Q_2|.

Cierre bajo concatenación

Recuerden la definición: A1A2={ uv:u∈A1 y v∈A2 }A_1A_2 = \{\, uv : u \in A_1 \text{ y } v \in A_2 \,\}. Para decidir si ww está en A1A2A_1A_2 hay que encontrar un corte de ww en dos partes, la primera en A1A_1 y la segunda en A2A_2. La dificultad es que puede haber muchos cortes posibles y solo algunos sirven. Un NFA resuelve esto como resuelve todo: adivina dónde está el corte.

Teorema. Si A1A_1 y A2A_2 son lenguajes regulares sobre Σ\Sigma, entonces A1A2A_1A_2 es regular.

Demostración. Por construcción. Sean N1N_1 y N2N_2 como en el teorema anterior, con Q1Q_1 y Q2Q_2 sin estados en común.

Qué se construye: el NFA N=(Q1∪Q2,Σ,δ,q1,F2)N = (Q_1 \cup Q_2, \Sigma, \delta, q_1, F_2). Empieza en el estado inicial de N1N_1 y sus estados de aceptación son solo los de N2N_2. La función δ\delta es la de las dos máquinas, con una transición ε\varepsilon agregada desde cada estado de aceptación de N1N_1 hacia el inicial de N2N_2:

δ(q,y)={δ1(q,y)∪{q2}si q∈F1 e y=εδ1(q,y)si q∈Q1, en los demaˊs casosδ2(q,y)si q∈Q2\delta(q, y) = \begin{cases} \delta_1(q, y) \cup \{q_2\} & \text{si } q \in F_1 \text{ e } y = \varepsilon \\ \delta_1(q, y) & \text{si } q \in Q_1 \text{, en los demás casos} \\ \delta_2(q, y) & \text{si } q \in Q_2 \end{cases}
Esquema de la construcción. Dos recuadros, uno al lado del otro: N₁ a la izquierda y N₂ a la derecha. La flecha de inicio entra a q₁, el estado inicial de N₁. Los dos estados que eran de aceptación en N₁ están dibujados con un solo círculo punteado, porque ya no aceptan, y de cada uno sale una flecha ε punteada, en granate, hacia q₂, el estado inicial de N₂. Los estados de aceptación de N₂ conservan su doble círculoEsquema de la construcción. Dos recuadros, uno al lado del otro: N₁ a la izquierda y N₂ a la derecha. La flecha de inicio entra a q₁, el estado inicial de N₁. Los dos estados que eran de aceptación en N₁ están dibujados con un solo círculo punteado, porque ya no aceptan, y de cada uno sale una flecha ε punteada, en granate, hacia q₂, el estado inicial de N₂. Los estados de aceptación de N₂ conservan su doble círculo
La concatenación: al terminar un trozo de A₁ se puede saltar al inicio de N₂. Solo aceptan los estados de N₂.

Los estados de F1F_1 dejan de ser de aceptación: llegar al final de un trozo de A1A_1 ya no basta.

Por qué reconoce A1A2A_1A_2: en las dos direcciones.

Si w∈A1A2w \in A_1A_2, entonces w=uvw = uv con u∈A1u \in A_1 y v∈A2v \in A_2. Hay un camino en N1N_1 de q1q_1 a algún f∈F1f \in F_1 con etiqueta uu, y un camino en N2N_2 de q2q_2 a algún estado de F2F_2 con etiqueta vv. Uniéndolos con el paso de ff a q2q_2 con ε\varepsilon, queda un camino en NN de q1q_1 a un estado de F2F_2 con etiqueta uεv=uv=wu\varepsilon v = uv = w. Luego NN acepta ww.

Si NN acepta ww, hay un camino en NN de q1q_1 a un estado de F2F_2 con etiqueta ww. Empieza en Q1Q_1 y termina en Q2Q_2. Las únicas flechas de NN que van de Q1Q_1 a Q2Q_2 son las transiciones ε\varepsilon agregadas, y no hay ninguna flecha de Q2Q_2 a Q1Q_1. Entonces el camino cruza exactamente una vez, con un paso de algún f∈F1f \in F_1 a q2q_2. Antes del cruce, el camino está dentro de N1N_1 y va de q1q_1 a ff: si uu es su etiqueta, u∈A1u \in A_1. Después del cruce, está dentro de N2N_2 y va de q2q_2 a un estado de F2F_2: si vv es su etiqueta, v∈A2v \in A_2. Y w=uεv=uvw = u\varepsilon v = uv. Luego w∈A1A2w \in A_1A_2. ∎

Con Termina en 01 como primera máquina y cantidad par de unos como segunda:

$ build/combine concat machines/ends_01.dfa machines/even_ones.dfa
# Concatenación de machines/ends_01.dfa y machines/even_ones.dfa.
states: 1.q0 1.q1 1.q2 2.par 2.impar
alphabet: 0 1
start: 1.q0
accept: 2.par
delta:
1.q0 0 1.q1
1.q0 1 1.q0
1.q1 0 1.q1
1.q1 1 1.q2
1.q2 0 1.q1
1.q2 1 1.q0
1.q2 eps 2.par
2.par 0 2.par
2.par 1 2.impar
2.impar 0 2.impar
2.impar 1 2.par

La única línea nueva es 1.q2 eps 2.par.

$ build/combine concat machines/ends_01.dfa machines/even_ones.dfa | build/run_nfa - 0111 011
w = 0111
  {1.q0} -0-> {1.q1} -1-> {1.q2,2.par} -1-> {1.q0,2.impar} -1-> {1.q0,2.par}
  termina con {1.q0,2.par} activos, y 2.par está en F: acepta
w = 011
  {1.q0} -0-> {1.q1} -1-> {1.q2,2.par} -1-> {1.q0,2.impar}
  termina con {1.q0,2.impar} activos, y ninguno está en F: rechaza

Después de leer 01\mathtt{01}, la primera máquina está en su estado de aceptación y la clausura ε\varepsilon activa a 2.par: una copia apuesta a que el corte está ahí, y otra sigue en la primera máquina por si el corte está más adelante. 0111\mathtt{0111} se acepta con el corte 01⋅11\mathtt{01} \cdot \mathtt{11}. 011\mathtt{011} no: el único corte con la primera parte terminada en 01\mathtt{01} deja 1\mathtt{1}, que tiene una cantidad impar de unos.

Error común. En la concatenación, dejar los estados de F1F_1 como estados de aceptación. Con eso se aceptarían cadenas de A1A_1 que no tienen ninguna continuación en A2A_2. Solo son de aceptación los de F2F_2. Si ε∈A2\varepsilon \in A_2, las cadenas de A1A_1 quedan aceptadas de todos modos, de la manera correcta: por la transición ε\varepsilon se llega a q2q_2, que en ese caso está en F2F_2 o alcanza a F2F_2 sin leer nada.

test_closure compara esta construcción con el predicado directo, “existe un corte w=uvw = uv con u∈A1u \in A_1 y v∈A2v \in A_2”, probando todos los cortes de cada cadena.

Cierre bajo estrella

Una cadena está en A∗A^* si se puede partir en cero o más trozos, cada uno de AA. Es la concatenación repetida, y la construcción repite la idea: al terminar un trozo, una transición ε\varepsilon permite volver al principio para empezar otro.

Teorema. Si AA es un lenguaje regular, entonces A∗A^* es regular.

Demostración. Por construcción. Sea N1=(Q1,Σ,δ1,q1,F1)N_1 = (Q_1, \Sigma, \delta_1, q_1, F_1) un NFA con L(N1)=AL(N_1) = A.

Qué se construye: el NFA N=(Q1∪{s},Σ,δ,s,F1∪{s})N = (Q_1 \cup \{s\}, \Sigma, \delta, s, F_1 \cup \{s\}), donde ss es un estado nuevo, y:

δ(q,y)={{q1}si q=s e y=ε∅si q=s e y≠εδ1(q,y)∪{q1}si q∈F1 e y=εδ1(q,y)en los demaˊs casos\delta(q, y) = \begin{cases} \{q_1\} & \text{si } q = s \text{ e } y = \varepsilon \\ \emptyset & \text{si } q = s \text{ e } y \neq \varepsilon \\ \delta_1(q, y) \cup \{q_1\} & \text{si } q \in F_1 \text{ e } y = \varepsilon \\ \delta_1(q, y) & \text{en los demás casos} \end{cases}

Son tres cambios: un estado inicial nuevo ss, que es de aceptación; una transición ε\varepsilon de ss al inicial anterior; y una transición ε\varepsilon de cada estado de aceptación al inicial anterior.

Esquema de la construcción. A la izquierda, un estado nuevo s, con la flecha de inicio y doble círculo. De s sale una flecha ε punteada hacia q₁, el estado inicial de N₁, que está dentro de un recuadro junto con sus dos estados de aceptación. De cada estado de aceptación sale una flecha ε punteada que vuelve a q₁, una por arriba y otra por abajo. El estado s y las flechas ε, que son lo nuevo, están en granateEsquema de la construcción. A la izquierda, un estado nuevo s, con la flecha de inicio y doble círculo. De s sale una flecha ε punteada hacia q₁, el estado inicial de N₁, que está dentro de un recuadro junto con sus dos estados de aceptación. De cada estado de aceptación sale una flecha ε punteada que vuelve a q₁, una por arriba y otra por abajo. El estado s y las flechas ε, que son lo nuevo, están en granate
La estrella: s acepta la cadena vacía, y al terminar un trozo de A se puede volver a q₁ para empezar otro.

Por qué reconoce A∗A^*: en las dos direcciones.

Si w∈A∗w \in A^*, entonces w=u1u2⋯ukw = u_1u_2 \cdots u_k con k≥0k \geq 0 y cada ui∈Au_i \in A. Si k=0k = 0, w=εw = \varepsilon, y NN la acepta con el camino de cero pasos, porque s∈Fs \in F. Si k≥1k \geq 1, para cada uiu_i hay un camino en N1N_1 de q1q_1 a algún fi∈F1f_i \in F_1 con etiqueta uiu_i. Se arma un camino en NN: el paso de ss a q1q_1 con ε\varepsilon; el camino de u1u_1 hasta f1f_1; el paso de f1f_1 a q1q_1 con ε\varepsilon; el camino de u2u_2; y así hasta llegar a fkf_k. Su etiqueta es u1u2⋯uk=wu_1u_2 \cdots u_k = w y termina en fk∈Ff_k \in F.

Si NN acepta ww, hay un camino en NN de ss a un estado de FF con etiqueta ww. Si tiene cero pasos, w=ε∈A∗w = \varepsilon \in A^*. Si tiene alguno, el primero es el paso de ss a q1q_1 con ε\varepsilon, porque de ss no sale otra flecha. Ninguna flecha entra a ss, así que el camino no vuelve a pasar por él: de ahí en adelante está en Q1Q_1 y termina en un estado de F1F_1. Cortemos ese resto en cada paso que no es una flecha de N1N_1. Esos pasos solo pueden ser las transiciones agregadas, que van de un estado de F1F_1 a q1q_1 con ε\varepsilon. Cada trozo que queda entre dos cortes empieza en q1q_1, usa solo flechas de N1N_1 y termina en un estado de F1F_1: el anterior al corte siguiente o, en el último trozo, el final del camino. Entonces la etiqueta de cada trozo, uiu_i, está en AA. Los cortes tienen etiqueta ε\varepsilon, así que w=u1u2⋯ukw = u_1u_2 \cdots u_k, con cada ui∈Au_i \in A: w∈A∗w \in A^*. ∎

Con machines/zeros_then_one.nfa, que reconoce las cadenas formadas por algunos ceros y después un solo 1\mathtt{1}: 1\mathtt{1}, 01\mathtt{01}, 001\mathtt{001}…

$ build/show_nfa machines/zeros_then_one.nfa
Q  = {q0, q1}
Σ  = {0, 1}
q0 = q0
F  = {q1}

     δ   0     1     ε
->   q0  {q0}  {q1}  {}
   * q1  {}    {}    {}

no tiene transiciones ε: E(S) = S para todo conjunto S
$ build/combine star machines/zeros_then_one.nfa
# Estrella de machines/zeros_then_one.nfa.
states: s q0 q1
alphabet: 0 1
start: s
accept: s q1
delta:
s eps q0
q0 0 q0
q0 1 q1
q1 eps q0

Si AA es el lenguaje de la máquina original, A∗A^* son las cadenas que se parten en trozos de la forma “ceros y un 1\mathtt{1}”: la cadena vacía y todas las que terminan en 1\mathtt{1}.

$ build/combine star machines/zeros_then_one.nfa | build/run_nfa - '' 0101 0
w = ε
  {s,q0}
  termina con {s,q0} activos, y s está en F: acepta
w = 0101
  {s,q0} -0-> {q0} -1-> {q0,q1} -0-> {q0} -1-> {q0,q1}
  termina con {q0,q1} activos, y q1 está en F: acepta
w = 0
  {s,q0} -0-> {q0}
  termina con {q0} activos, y ninguno está en F: rechaza

La cadena vacía se acepta porque ss está activo antes de leer nada y es de aceptación. Eso pasa con cualquier N1N_1: ε∈A∗\varepsilon \in A^* siempre, y en la construcción el camino de cero pasos siempre acepta. La cadena 0\mathtt{0} se rechaza, como debe: no termina en 1\mathtt{1}. Después del primer símbolo, ss ya no vuelve a estar activo.

Por qué hace falta un estado inicial nuevo

El estado ss existe para una sola cosa: aceptar ε\varepsilon. Parece más barato ahorrárselo.

Un intento que parece funcionar. No agregar ss. Marcar el estado inicial q1q_1 como de aceptación, para que se acepte ε\varepsilon, y agregar las transiciones ε\varepsilon de los estados de aceptación a q1q_1.

Dónde falla. Si alguna flecha de N1N_1 vuelve a q1q_1, hay cadenas que regresan al estado inicial a mitad de un trozo, sin haber completado ninguno. Al marcar q1q_1 como de aceptación, esas cadenas quedan aceptadas. En zeros_then_one.nfa, el estado inicial tiene una flecha hacia sí mismo con 0\mathtt{0}. La cadena 0\mathtt{0} deja a la máquina en q0q_0, que ahora sería de aceptación. Pero 0∉A∗\mathtt{0} \notin A^*.

El programa wrong_star aplica las dos construcciones, la correcta y la del intento, y lista las cadenas en las que no coinciden:

$ build/wrong_star machines/zeros_then_one.nfa 3
cadena   con estado inicial nuevo   sin estado inicial nuevo
0        rechaza                    acepta
00       rechaza                    acepta
10       rechaza                    acepta
000      rechaza                    acepta
010      rechaza                    acepta
100      rechaza                    acepta
110      rechaza                    acepta
7 cadenas de longitud a lo sumo 3 en las que no coinciden

Son todas las cadenas no vacías que terminan en 0\mathtt{0}: con el intento, la máquina acepta todo Σ∗\Sigma^*. El problema no es aceptar ε\varepsilon, sino que “estar en q1q_1” pasó a significar dos cosas a la vez: “todavía no empecé o acabo de terminar un trozo” y “estoy a mitad de un trozo que volvió a pasar por el principio”. El estado nuevo ss separa los dos significados: ss es de aceptación y q1q_1 sigue sin serlo.

Dos autómatas, uno al lado del otro, después de leer la cadena 0. A la izquierda, la construcción correcta sobre zeros_then_one: el estado nuevo s, inicial y de aceptación, con una flecha ε a q₀; q₀ con un bucle con 0 y una flecha con 1 a q₁, que es de aceptación; y una flecha ε de q₁ a q₀. Con 0, los activos pasan de {s, q₀} a {q₀}; q₀ no está en F y la cadena se rechaza. A la derecha, el intento sin estado nuevo: q₀ es inicial y está marcado como de aceptación, con el mismo bucle con 0, la flecha con 1 a q₁ y la flecha ε de vuelta. Con 0, los activos pasan de {q₀} a {q₀}; q₀ ahora está en F y la cadena se acepta, aunque 0 no está en A*Dos autómatas, uno al lado del otro, después de leer la cadena 0. A la izquierda, la construcción correcta sobre zeros_then_one: el estado nuevo s, inicial y de aceptación, con una flecha ε a q₀; q₀ con un bucle con 0 y una flecha con 1 a q₁, que es de aceptación; y una flecha ε de q₁ a q₀. Con 0, los activos pasan de {s, q₀} a {q₀}; q₀ no está en F y la cadena se rechaza. A la derecha, el intento sin estado nuevo: q₀ es inicial y está marcado como de aceptación, con el mismo bucle con 0, la flecha con 1 a q₁ y la flecha ε de vuelta. Con 0, los activos pasan de {q₀} a {q₀}; q₀ ahora está en F y la cadena se acepta, aunque 0 no está en A*
El bucle de q₀ vuelve al estado inicial a mitad de un trozo. Si q₀ acepta, esa cadena queda aceptada sin haber completado ningún trozo.

Error común. Construir la estrella marcando el estado inicial como de aceptación en lugar de agregar uno nuevo. Solo es correcto cuando ninguna flecha entra al estado inicial, y es más fácil agregar el estado siempre que revisar esa condición.

Cierre bajo reverso

El reverso de un lenguaje es AR={ wR:w∈A }A^R = \{\, w^R : w \in A \,\}: las cadenas de AA leídas de derecha a izquierda. Si AA es termina en 01, ARA^R es empieza con 10.

La idea de la construcción es recorrer la máquina hacia atrás: empezar donde terminaba, seguir las flechas en sentido contrario y aceptar al llegar adonde empezaba. Con un DFA eso tropieza enseguida. Al invertir las flechas, de un estado pueden salir varias con el mismo símbolo, o ninguna, y si había varios estados de aceptación habría varios estados iniciales. Todo eso es justo lo que un NFA permite.

Construcción. Sea N1=(Q1,Σ,δ1,q1,F1)N_1 = (Q_1, \Sigma, \delta_1, q_1, F_1) un NFA con L(N1)=AL(N_1) = A. Se define N=(Q1∪{s},Σ,δ,s,{q1})N = (Q_1 \cup \{s\}, \Sigma, \delta, s, \{q_1\}), con ss un estado nuevo, y:

  • Las flechas, al revés: para p,r∈Q1p, r \in Q_1 y toda etiqueta y∈Σ∪{ε}y \in \Sigma \cup \{\varepsilon\}, p∈δ(r,y)p \in \delta(r, y) si y solo si r∈δ1(p,y)r \in \delta_1(p, y).
  • El inicio: δ(s,ε)=F1\delta(s, \varepsilon) = F_1. Desde el estado nuevo se salta, sin leer nada, a cualquiera de los estados que eran de aceptación.
  • El final: el único estado de aceptación es q1q_1, el que era inicial.

Por qué reconoce ARA^R. La clave es una sola observación: una secuencia de estados r0,r1,…,rmr_0, r_1, \ldots, r_m con etiquetas y1,…,ymy_1, \ldots, y_m es un camino en N1N_1 si y solo si la secuencia invertida, rm,…,r1,r0r_m, \ldots, r_1, r_0 con etiquetas ym,…,y1y_m, \ldots, y_1, es un camino por las flechas invertidas de NN. Y si las etiquetas del primero forman ww, las del segundo forman wRw^R. Entonces hay un camino en N1N_1 de q1q_1 a algún f∈F1f \in F_1 con etiqueta ww exactamente cuando hay un camino en NN de ff a q1q_1 con etiqueta wRw^R, y a ese se le antepone el paso de ss a ff. Los detalles, en particular por qué un camino que acepta en NN no pasa dos veces por ss, quedan como ejercicio.

$ build/combine reverse machines/ends_01.dfa
# Reverso de machines/ends_01.dfa.
states: s q0 q1 q2
alphabet: 0 1
start: s
accept: q0
delta:
s eps q2
q0 1 q0 q2
q1 0 q0 q1 q2
q2 1 q1

El DFA original tenía tres flechas con 0\mathtt{0} que llegaban a q1q_1, desde q0q_0, q1q_1 y q2q_2. Invertidas, son tres flechas con 0\mathtt{0} que salen de q1q_1: la línea q1 0 q0 q1 q2. Y de q2q_2 ya no sale nada con 0\mathtt{0}. El reverso de un DFA no es un DFA.

$ build/combine reverse machines/ends_01.dfa | build/run_nfa - 100 010
w = 100
  {s,q2} -1-> {q1} -0-> {q0,q1,q2} -0-> {q0,q1,q2}
  termina con {q0,q1,q2} activos, y q0 está en F: acepta
w = 010
  {s,q2} -0-> {} -1-> {} -0-> {}
  termina con {} activos, y ninguno está en F: rechaza

100\mathtt{100} empieza con 10\mathtt{10}: su reverso, 001\mathtt{001}, termina en 01\mathtt{01}. test_closure comprueba, con este autómata, con el del tercer símbolo desde el final y con 100 NFA al azar, que el autómata invertido acepta ww exactamente cuando el original acepta wRw^R.

El reverso explica algo del primer ejemplo del capítulo. El reverso de TT, el tercer símbolo desde el final es 1, es el tercer símbolo es 1, que tiene un DFA de 5 estados: cuenta tres símbolos, mira el tercero y pasa a un estado “sí” o a un estado “no” de los que no sale. Leer de izquierda a derecha un lenguaje que se define desde el final es lo que le cuesta al DFA. Invertir un DFA pequeño puede dar un lenguaje cuyo DFA más pequeño es exponencialmente mayor.

El complemento no se hace en el NFA

Con unión, concatenación, estrella y reverso, parece que cualquier operación sale más fácil con un NFA. Hay una que no. La semana pasada, el complemento fue la construcción más corta: cambiar FF por Q−FQ - F.

Un intento que parece funcionar. Hacer lo mismo con un NFA: dejar la máquina igual e intercambiar los estados de aceptación.

Dónde falla. El programa swap_accept lo prueba con el autómata del tercer símbolo desde el final, cuyo único estado de aceptación es q3q_3:

$ build/swap_accept machines/third_from_end.nfa 100 000
F = {q3}    Q − F = {q0,q1,q2}
w = 100
  activos al final: {q0,q3}
  el NFA:                        acepta
  el NFA con Q − F:              acepta
  el DFA de subconjuntos, Q − F: rechaza
w = 000
  activos al final: {q0}
  el NFA:                        rechaza
  el NFA con Q − F:              acepta
  el DFA de subconjuntos, Q − F: acepta

La cadena 100\mathtt{100} está en TT, así que no debería estar en el complemento. Pero el NFA con los estados intercambiados también la acepta. Después de leerla hay dos estados activos, q0q_0 y q3q_3. Antes del intercambio se aceptaba por q3q_3. Después del intercambio se acepta por q0q_0. De hecho q0q_0 está activo siempre, así que el NFA intercambiado acepta todas las cadenas: reconoce Σ∗\Sigma^*, que no es el complemento de TT.

La razón está en la definición de aceptar, y es una cuestión de lógica. NN acepta ww si algún camino termina en FF. Entonces ww está en el complemento si ningún camino termina en FF, es decir, si todos los caminos que leen ww terminan fuera de FF o mueren. Intercambiar los estados de aceptación da otra cosa: un NFA que acepta si algún camino termina fuera de FF. Negar “existe” da “para todo”, y un NFA solo sabe decir “existe”.

En un DFA el problema no aparece porque hay un solo camino: “alguno” y “todos” son lo mismo. La demostración de la semana pasada usó exactamente eso, que δ∗(q0,w)\delta^*(q_0, w) existe y es un solo estado.

Error común. Complementar un NFA intercambiando sus estados de aceptación. La manera correcta tiene dos pasos: primero la construcción de subconjuntos, y después el intercambio en el DFA. Es la última línea de cada bloque en la salida de swap_accept. En el DFA, el estado {q0,q3}\{q_0, q_3\} es de aceptación porque contiene a q3q_3; al intercambiar deja de serlo, y 100\mathtt{100} se rechaza.

El costo es el de la construcción de subconjuntos: el complemento de un lenguaje con un NFA de nn estados puede necesitar un DFA de hasta 2n2^n. Los lenguajes regulares son cerrados bajo complemento, y lo demostramos la semana pasada. Lo que no hay es una construcción barata sobre NFA. La intersección tampoco necesita pasar por un DFA: el producto funciona con dos NFA, y queda como ejercicio.

Con esto, la lista de propiedades de cierre de los lenguajes regulares queda así:

Operación Construcción Estados
Unión Producto de dos DFA, o NFA con un estado inicial nuevo ∣Q1∣⋅∣Q2∣\lvert Q_1\rvert \cdot \lvert Q_2\rvert, o ∣Q1∣+∣Q2∣+1\lvert Q_1\rvert + \lvert Q_2\rvert + 1
Intersección Producto ∣Q1∣⋅∣Q2∣\lvert Q_1\rvert \cdot \lvert Q_2\rvert
Complemento Intercambiar FF en un DFA ∣Q∣\lvert Q\rvert
Concatenación NFA con transiciones ε\varepsilon de F1F_1 a q2q_2 ∣Q1∣+∣Q2∣\lvert Q_1\rvert + \lvert Q_2\rvert
Estrella NFA con un estado inicial nuevo ∣Q1∣+1\lvert Q_1\rvert + 1
Reverso NFA con las flechas invertidas ∣Q1∣+1\lvert Q_1\rvert + 1

La unión, la concatenación y la estrella se llaman operaciones regulares. La semana próxima veremos que con ellas tres, partiendo de los lenguajes más simples posibles, se obtienen todos los lenguajes regulares: eso son las expresiones regulares. Las tres construcciones de este capítulo serán entonces las piezas de un algoritmo que convierte una expresión regular en un NFA.

El código de la semana

code/week-02/
├── nfa.h                 struct Nfa, formato .nfa, clausura ε, δ*, subconjuntos y las construcciones de cierre
├── dfa.h                 el struct Dfa de la semana 1, sin cambios
├── kth.h                 el NFA de "el k-ésimo símbolo desde el final es 1"
├── strings.h, print.h    ayudas: todas las cadenas hasta una longitud, tablas alineadas
├── show_nfa.cpp          muestra un .nfa como quíntupla y como tabla, con la clausura ε de cada estado
├── run_nfa.cpp           el conjunto de estados activos después de cada símbolo
├── paths_nfa.cpp         todos los caminos de un NFA con una cadena, uno por línea
├── subset.cpp            la tabla de la construcción de subconjuntos
├── nfa_to_dfa.cpp        la construcción de subconjuntos, con salida en formato .dfa
├── run_dfa.cpp           el programa de la semana 1, para seguir el DFA construido
├── combine.cpp           unión, concatenación, estrella y reverso de archivos .nfa
├── kth_nfa.cpp           escribe el NFA de kth.h para un k
├── kth_table.cpp         la tabla de estados para k de 1 a 12
├── wrong_star.cpp        la estrella sin estado inicial nuevo, comparada con la correcta
├── swap_accept.cpp       intercambiar F en un NFA, comparado con el complemento correcto
├── machines/             los autómatas del capítulo, en formato .nfa y .dfa
├── errors/               las dos construcciones incorrectas y dos archivos que no son un NFA
├── test_helpers.h        predicados, aceptación por caminos y NFA al azar para las pruebas
├── test_nfa.cpp          cada NFA contra un predicado; estados activos contra la definición por caminos
├── test_subset.cpp       el DFA construido contra el NFA; la tabla de k de 1 a 12
├── test_closure.cpp      las cuatro construcciones contra su predicado; las dos incorrectas
└── lab/nfa_to_dfa/       el laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan. Tardan bastante más que las de la semana pasada, porque recorren muchas cadenas con conjuntos de nombres y con los sanitizers activos.

$ make test
test_nfa: ok (7 autómatas, 15562 cadenas en total; 200 NFA al azar contra la definición)
test_subset: ok (4 autómatas de los apuntes, k de 1 a 12, 200 NFA al azar)
test_closure: ok (unión, concatenación, estrella y reverso; 100 pares de NFA al azar)
Todas las pruebas pasaron.

Las pruebas comprueban con assert lo que este capítulo afirma.

  • test_nfa compara cada autómata de machines/ con una función de C++ que decide el mismo lenguaje mirando la cadena completa. Comprueba los conjuntos de estados activos copiados en estos apuntes, las propiedades de la clausura ε\varepsilon y el lema de los estados activos: la simulación con conjuntos contra una búsqueda directa de un camino.
  • test_subset comprueba el lema de la construcción y el teorema: para cada cadena, el estado del DFA es el conjunto de estados activos del NFA, y aceptan lo mismo. Revisa la cantidad de estados de cada ejemplo, que el NFA de Termina en 01 da el DFA de la semana pasada, y que para kk de 1 a 12 salen exactamente 2k2^k.
  • test_closure compara la unión, la concatenación, la estrella y el reverso con el predicado que define cada operación, calculado sin autómatas: “está en alguno de los dos”, “existe un corte”, “se parte en trozos”, “su reverso está”. Y comprueba que las dos construcciones incorrectas fallan con las cadenas de este capítulo: la estrella sin estado nuevo acepta 0\mathtt{0}, y el NFA con FF intercambiado acepta 100\mathtt{100}.

Los archivos de machines/ son:

Archivo Lenguaje Estados Estados del DFA construido
third_from_end.nfa El tercer símbolo desde el final es 1\mathtt{1} 4 8
contains_101_or_11.nfa Contiene 101\mathtt{101} o 11\mathtt{11}, con una transición ε\varepsilon 4 6
abc_blocks.nfa Algunas a\mathtt{a}, después b\mathtt{b}, después c\mathtt{c} 3 4
ends_01.nfa Termina en 01\mathtt{01} 3 3
zeros_then_one.nfa Algunos ceros y un 1\mathtt{1} 2 3
even_ones.dfa, ends_01.dfa Los DFA de la semana 1, para combinarlos 2 y 3

En errors/ hay dos archivos que show_nfa no acepta, y un encabezado con las dos construcciones incorrectas:

$ build/show_nfa errors/unknown_state.nfa
error: errors/unknown_state.nfa: no es un NFA: transición hacia q2, que no está en states

Para experimentar, copien un archivo de machines/, agréguenle una transición ε\varepsilon y vuelvan a correr run_nfa y subset con las mismas cadenas.

El laboratorio

En lab/nfa_to_dfa está el enunciado, un esqueleto, los casos y un verificador. El problema es la construcción de subconjuntos: la entrada es un NFA en formato .nfa, con transiciones ε\varepsilon, y la salida es un DFA equivalente en formato .dfa.

cd lab/nfa_to_dfa
make        # compila solution.cpp
make test   # corre el juez con todos los casos

Hay muchas respuestas correctas, porque los estados del DFA pueden llamarse como ustedes quieran. Por eso el juez no compara su salida con un archivo: usa verificador.cpp, que comprueba que lo que entregaron es un DFA bien formado y que reconoce el mismo lenguaje que el NFA. Para eso recorre las dos máquinas a la vez, como en el producto, buscando un par alcanzable en el que una acepte y la otra no. Si lo encuentra, les muestra la cadena.

nfa.h ya trae la construcción, y pueden leerla. El laboratorio pide escribirla de nuevo, sin incluir ese archivo, de modo que aguante un NFA de 60 estados: el enunciado limita el DFA a 10 000 estados, y un programa que genera los 2n2^n subconjuntos no pasa. La última parte del laboratorio es llenar con su programa la tabla de kk de 1 a 12 de la sección El costo: hasta 2ⁿ estados.

Resumen

  • Un NFA es N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F) con δ:Q×(Σ∪{ε})→P(Q)\delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q): la función de transición devuelve un conjunto de estados, que puede ser vacío. Puede haber varias flechas con un símbolo, ninguna, y transiciones ε\varepsilon, que no leen nada.
  • NN acepta ww si existe un camino de q0q_0 a un estado de FF cuyas etiquetas forman ww. Los caminos que mueren o terminan en otro lado no cuentan. No acepta “si todos los caminos aceptan” ni “al azar”.
  • Tres imágenes equivalentes: adivinar bien, explorar todos los caminos a la vez, y un árbol de ejecuciones.
  • La clausura ε\varepsilon E(S)E(S) es el conjunto de estados alcanzables desde SS con cero o más transiciones ε\varepsilon. Se calcula con un recorrido del grafo de las flechas ε\varepsilon.
  • Para simular un NFA se sigue el conjunto de estados activos: δ∗(S,ε)=E(S)\delta^*(S, \varepsilon) = E(S) y δ∗(S,xa)=E(⋃q∈δ∗(S,x)δ(q,a))\delta^*(S, xa) = E\bigl(\bigcup_{q \in \delta^*(S, x)} \delta(q, a)\bigr). NN acepta ww si y solo si δ∗({q0},w)\delta^*(\{q_0\}, w) contiene algún estado de FF.
  • Todo DFA es un NFA. Y al revés: la construcción de subconjuntos da, para todo NFA, un DFA equivalente. Sus estados son conjuntos de estados del NFA, el inicial es E({q0})E(\{q_0\}), la transición es δD(S,a)=E(⋃q∈Sδ(q,a))\delta_D(S, a) = E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr), y son de aceptación los conjuntos que contienen algún estado de FF. El conjunto ∅\emptyset es el estado trampa.
  • La equivalencia se demuestra con dos lemas por inducción sobre la longitud: los estados activos son los estados con un camino, y el DFA queda en el conjunto de estados activos.
  • Un lenguaje es regular si y solo si algún NFA lo reconoce. Para demostrar que un lenguaje es regular basta dar un NFA.
  • Solo se construyen los subconjuntos alcanzables, con una cola. Aun así pueden ser 2n2^n: el lenguaje “el kk-ésimo símbolo desde el final es 1\mathtt{1}” tiene un NFA de k+1k + 1 estados y todo DFA suyo tiene al menos 2k2^k. La demostración de esa cota es de la semana 4.
  • Los lenguajes regulares son cerrados bajo unión (estado inicial nuevo con dos transiciones ε\varepsilon), concatenación (transiciones ε\varepsilon de F1F_1 a q2q_2, y F=F2F = F_2), estrella (estado inicial nuevo de aceptación, y transiciones ε\varepsilon de F1F_1 a q1q_1) y reverso (flechas invertidas).
  • En la estrella, el estado inicial nuevo es necesario: marcar el anterior como de aceptación acepta cadenas de más cuando alguna flecha vuelve a él.
  • El complemento no se obtiene intercambiando los estados de aceptación de un NFA. Primero se convierte a DFA.

Ejercicios

  1. Con el autómata de machines/third_from_end.nfa, escriban a mano todos los caminos para 1011\mathtt{1011} y digan cuáles terminan en FF, cuáles terminan fuera y cuáles mueren. Después calculen el conjunto de estados activos después de cada símbolo. Comprueben con paths_nfa y con run_nfa. ¿Cuántos caminos tiene la cadena 1n\mathtt{1}^n?
  2. Sigan a mano el autómata de machines/contains_101_or_11.nfa con 10011\mathtt{10011}, con una tabla como la de la sección Seguir un NFA: el conjunto de estados activos: los destinos de las flechas y el conjunto después de la clausura. ¿En qué fila cambia algo si se borra la transición ε\varepsilon? ¿Qué lenguaje reconoce la máquina sin ella?
  3. Diseñen un NFA para cada lenguaje sobre {0,1}\{\mathtt{0}, \mathtt{1}\}, con la cantidad de estados indicada, y escriban el archivo .nfa: (a) las cadenas que contienen 0110\mathtt{0110}, con 5 estados; (b) las que terminan en 00\mathtt{00} o en 11\mathtt{11}, con 5 estados o menos; (c) las que tienen un 1\mathtt{1} en la segunda posición o en la penúltima. En cada uno digan qué adivina la máquina.
  4. En el NFA de machines/abc_blocks.nfa, calculen E(S)E(S) para los ocho subconjuntos SS de {qa,qb,qc}\{q_a, q_b, q_c\}. ¿Cuántos resultados distintos hay? Demuestren, a partir de la definición, que E(E(S))=E(S)E(E(S)) = E(S) y que E(S1∪S2)=E(S1)∪E(S2)E(S_1 \cup S_2) = E(S_1) \cup E(S_2) en cualquier NFA.
  5. Apliquen a mano la construcción de subconjuntos al NFA de machines/zeros_then_one.nfa y al resultado de build/combine star machines/zeros_then_one.nfa. Dibujen solo los estados alcanzables y comprueben con subset. En el segundo, ¿qué dos estados del DFA se podrían juntar en uno sin cambiar el lenguaje?
  6. ¿Por qué los estados de aceptación del DFA construido son los subconjuntos que contienen algún estado de FF? Construyan el DFA de machines/ends_01.nfa con la regla equivocada “el subconjunto está contenido en FF” y den una cadena con la que falla. ¿Qué lenguaje reconoce un NFA si se cambia la definición de aceptar por “todos los caminos que leen la cadena completa terminan en FF, y hay al menos uno”?
  7. Demuestren que para todo NFA hay un NFA equivalente sin transiciones ε\varepsilon y con los mismos estados. Sugerencia: definan δ′(q,a)=E(⋃r∈E({q})δ(r,a))\delta'(q, a) = E\bigl(\bigcup_{r \in E(\{q\})} \delta(r, a)\bigr) y decidan cuáles deben ser los estados de aceptación para que la cadena vacía se siga aceptando cuando corresponde. Aplíquenlo a machines/abc_blocks.nfa.
  8. Con combine, construyan el NFA de la concatenación de cantidad par de unos con termina en 01, en ese orden. ¿Qué lenguaje es, descrito con palabras? Sigan 1101\mathtt{1101} con run_nfa y digan qué corte usa el camino que acepta. Después apliquen subset y cuenten los estados.
  9. Den un NFA, distinto del de estos apuntes, para el que intercambiar los estados de aceptación no dé el complemento, y una cadena que lo muestre. Después den un NFA que no sea un DFA para el que el intercambio sí dé el complemento. ¿Qué propiedad de sus caminos lo explica?
  10. Completen la demostración del cierre bajo reverso: demuestren por inducción sobre la cantidad de pasos que una secuencia es un camino en N1N_1 con etiqueta ww si y solo si la secuencia invertida es un camino por las flechas invertidas con etiqueta wRw^R. Usen que (uv)R=vRuR(uv)^R = v^Ru^R, del ejercicio 4 de la semana pasada. Después demuestren que un camino de NN que acepta usa el estado ss una sola vez.
  11. La construcción del producto también funciona con dos NFA sin transiciones ε\varepsilon: δ((p,q),a)=δ1(p,a)×δ2(q,a)\delta((p, q), a) = \delta_1(p, a) \times \delta_2(q, a) y F=F1×F2F = F_1 \times F_2. Demuestren que reconoce L(N1)∩L(N2)L(N_1) \cap L(N_2). ¿Por qué la misma máquina con “alguno acepta” no reconoce siempre la unión? Den un ejemplo. Sugerencia: piensen en un camino que muere en una de las dos máquinas.
  12. Demuestren que si AA es regular, también lo son: (a) el lenguaje de los prefijos de las cadenas de AA; (b) el de los sufijos; (c) el de las subcadenas. En cada caso modifiquen un NFA de AA y digan qué cambia. Sugerencia para (a): ¿desde qué estados se puede llegar a un estado de aceptación?
  13. Para programar. Agreguen a nfa.h una función remove_eps que haga la construcción del ejercicio 7, y una prueba que la compare con el NFA original en todas las cadenas hasta longitud 8, para los autómatas de machines/. ¿Cambia la cantidad de estados del DFA que da subset_construction?
  14. Para programar. Escriban un programa que reciba kk y un patrón binario xx de longitud kk, construya el NFA de “contiene xx” con k+1k + 1 estados y le aplique la construcción de subconjuntos. Cuenten los estados alcanzables para varios patrones de longitud 8. ¿Por qué aquí no aparece el 2k2^k? Comparen con la tabla de kth_table y expliquen la diferencia entre los dos lenguajes en términos de lo que el DFA tiene que recordar.