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

Apuntes · Capítulo 3Lenguajes regulares

Expresiones regulares

Expresiones regulares

Hasta aquí, un lenguaje regular se dio siempre con una máquina. En la semana 1 fue un DFA: una tabla que dice qué hacer con cada símbolo. La semana pasada fue un NFA, que puede adivinar y por eso suele ser más pequeño, y vimos que adivinar no agrega ningún lenguaje: la construcción de subconjuntos convierte cualquier NFA en un DFA. En los dos casos, quien quiere saber qué lenguaje reconoce la máquina tiene que ejecutarla en la cabeza.

Esta semana aparece la tercera manera de dar un lenguaje regular, y es de otro tipo. Una expresión regular no dice cómo reconocer las cadenas: dice cómo son. La expresión (0∪1)∗1(\mathtt{0} \cup \mathtt{1})^*\mathtt{1} se lee de corrido: cualquier cantidad de ceros y unos, y al final un uno. Es la notación que usan grep, los editores de texto y los validadores de formularios, y la que usa un compilador para decir qué forma tiene un número o un identificador.

Las dos preguntas de la semana son las dos direcciones entre describir y reconocer.

  • De la descripción a la máquina. Dada una expresión, ¿se puede construir un autómata que reconozca exactamente las cadenas que describe? Sí, y la construcción es mecánica: una pieza de NFA por cada operación. Es lo que hace grep cada vez que lo usan.
  • De la máquina a la descripción. Dado un autómata, ¿hay una expresión que describa su lenguaje? También, y esta dirección cuesta más: se eliminan los estados uno por uno, y las flechas van acumulando expresiones.

Las dos respuestas juntas son el teorema de Kleene: los DFA, los NFA y las expresiones regulares describen exactamente los mismos lenguajes. Con eso la clase de los lenguajes regulares queda definida de tres maneras independientes, y se puede elegir en cada problema la que convenga.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Describir en vez de reconocer y La definición de expresión regular. Antes de la sesión B, La dirección difícil y Autómatas con expresiones en las flechas.

En clase: Sesión A, de Describir en vez de reconocer a Las abreviaturas de las herramientas. Sesión B, de La dirección difícil a Cómo busca un motor real.

Después de clase: el Resumen y los Ejercicios, para repasar. Antes del laboratorio, De expresión regular a NFA: la construcción de Thompson otra vez, Cómo busca un motor real y El código de la semana. Para ampliar, las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, sec. 1.3 (Regular Expressions); su segunda mitad trata los autómatas generalizados (GNFA) de la sesión B. Erickson, Models of Computation, notas 2 (Regular languages) y 4. Son apoyo: estos apuntes se pueden estudiar solos.

Código. Los programas de este capítulo están en code/week-03. 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/mini_grep.

Describir en vez de reconocer

Supongan que quieren encontrar, en un archivo de registro de un millón de líneas, las que tienen una fecha. Nadie escribe para eso la tabla de transiciones de un autómata. Se escribe algo como esto:

[0-9][0-9]/[0-9][0-9]/[0-9][0-9][0-9][0-9]

Dos dígitos, una barra, dos dígitos, una barra, cuatro dígitos. El patrón no dice en qué orden mirar los caracteres ni qué recordar: dice qué forma tiene lo que se busca. La herramienta se encarga del resto.

Esa manera de trabajar está en muchos sitios.

  • grep y los editores. grep recibe un patrón y un archivo, e imprime las líneas en las que el patrón aparece. El nombre viene de un comando del editor ed: g/re/p, por global, regular expression y print. Buscar y reemplazar con patrones en cualquier editor de código es lo mismo.
  • Los validadores. Un formulario web comprueba que un campo tenga forma de código postal o de número de teléfono comparándolo con un patrón.
  • Los lexers. La primera fase de un compilador parte el texto del programa en tokens: identificadores, números, operadores. La forma de cada token se da con una expresión regular, y una herramienta genera el autómata que los reconoce.

En los tres casos pasa lo mismo: la persona escribe una descripción, y un programa la convierte en una máquina que lee el texto. La sesión A estudia las descripciones y esa conversión. La sesión B demuestra que no se pierde nada en el cambio: todo lo que una máquina de estados finitos reconoce se puede describir así.

La notación de las herramientas tiene muchos operadores, y cada herramienta agrega los suyos. La teoría se queda con tres, y con ellos alcanza. Los demás, como los corchetes y las llaves del ejemplo, son abreviaturas, y al final de la sesión A veremos por qué no agregan nada.

Una advertencia sobre la escritura, que vale para todo el capítulo. En la teoría, la unión se escribe con ∪\cup: (0∪1)∗1(\mathtt{0} \cup \mathtt{1})^*\mathtt{1}. En el teclado, en las herramientas y en el código del curso, la unión se escribe con la barra vertical: (0|1)*1. Es la misma expresión. En estos apuntes, las fórmulas usan ∪\cup, y lo que se escribe en la terminal y lo que imprimen los programas usa |.

La definición de expresión regular

En la semana 1 definimos tres operaciones sobre lenguajes que se llaman operaciones regulares: la unión A∪BA \cup B, la concatenación ABAB y la estrella A∗A^*. La semana pasada demostraron que los lenguajes regulares son cerrados bajo las tres. Una expresión regular es una fórmula escrita con esas tres operaciones, a partir de los lenguajes más simples que hay.

La definición es inductiva, como la de las cadenas en la semana 1: dice cuáles son las expresiones más pequeñas y cómo se arman las más grandes a partir de otras ya armadas.

Definición. Sea Σ\Sigma un alfabeto. RR es una expresión regular (regular expression) sobre Σ\Sigma si RR es de una de estas seis formas:

  1. aa, para algún símbolo aa de Σ\Sigma;
  2. ε\varepsilon;
  3. ∅\emptyset;
  4. (R1∪R2)(R_1 \cup R_2), donde R1R_1 y R2R_2 son expresiones regulares;
  5. (R1R2)(R_1 R_2), donde R1R_1 y R2R_2 son expresiones regulares;
  6. (R1∗)(R_1^*), donde R1R_1 es una expresión regular.

Los casos 1 a 3 son los casos base. Los casos 4 a 6 construyen una expresión a partir de otras más pequeñas. La definición no es circular: toda expresión se termina descomponiendo en símbolos, ε\varepsilon y ∅\emptyset, igual que toda cadena se termina descomponiendo hasta llegar a la cadena vacía.

Una expresión es un texto, una fórmula. Lo que interesa es el lenguaje que describe, que se escribe L(R)L(R) y se define siguiendo los mismos seis casos:

Expresión RR Lenguaje L(R)L(R) En palabras
aa {a}\{a\} Solo la cadena de un símbolo aa
ε\varepsilon {ε}\{\varepsilon\} Solo la cadena vacía
∅\emptyset ∅\emptyset Ninguna cadena
(R1∪R2)(R_1 \cup R_2) L(R1)∪L(R2)L(R_1) \cup L(R_2) Las cadenas de R1R_1 y las de R2R_2
(R1R2)(R_1 R_2) L(R1)L(R2)L(R_1)L(R_2) Una cadena de R1R_1 seguida de una de R2R_2
(R1∗)(R_1^*) L(R1)∗L(R_1)^* Cero o más cadenas de R1R_1, una tras otra

Con Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\}, la expresión ((0∪1)∗)((\mathtt{0} \cup \mathtt{1})^*) se arma en tres pasos y su lenguaje se calcula en los mismos tres:

L(0)={0},L(1)={1}caso 1L((0∪1))={0}∪{1}={0,1}caso 4L(((0∪1)∗))={0,1}∗=Σ∗caso 6\begin{aligned} L(\mathtt{0}) &= \{\mathtt{0}\}, \quad L(\mathtt{1}) = \{\mathtt{1}\} && \text{caso 1} \\ L((\mathtt{0} \cup \mathtt{1})) &= \{\mathtt{0}\} \cup \{\mathtt{1}\} = \{\mathtt{0}, \mathtt{1}\} && \text{caso 4} \\ L(((\mathtt{0} \cup \mathtt{1})^*)) &= \{\mathtt{0}, \mathtt{1}\}^* = \Sigma^* && \text{caso 6} \end{aligned}

Tres cosas de la definición que conviene leer despacio.

  • Una expresión y su lenguaje son objetos distintos. RR es una fórmula finita, y L(R)L(R) es un conjunto de cadenas, casi siempre infinito. Dos expresiones distintas pueden describir el mismo lenguaje: (0∪1)(\mathtt{0} \cup \mathtt{1}) y (1∪0)(\mathtt{1} \cup \mathtt{0}) son fórmulas distintas con L={0,1}L = \{\mathtt{0}, \mathtt{1}\}. Cuando escribimos R1=R2R_1 = R_2 entre expresiones queremos decir L(R1)=L(R2)L(R_1) = L(R_2): que son equivalentes.
  • Los símbolos ε\varepsilon y ∅\emptyset tienen aquí un segundo uso. En la semana 1, ε\varepsilon era una cadena y ∅\emptyset un lenguaje. Dentro de una expresión regular los dos son expresiones: la expresión ε\varepsilon describe el lenguaje {ε}\{\varepsilon\}, y la expresión ∅\emptyset describe el lenguaje ∅\emptyset. Siguen siendo cosas opuestas, como entonces.
  • Las palabras. Una máquina reconoce un lenguaje. Una expresión lo describe. De una cadena de L(R)L(R) diremos que RR la describe, o que la cadena coincide con RR.

Dos abreviaturas que usaremos en la teoría. Si Σ={a1,…,ak}\Sigma = \{a_1, \ldots, a_k\}, dentro de una expresión se escribe Σ\Sigma en lugar de (a1∪⋯∪ak)(a_1 \cup \cdots \cup a_k): un símbolo cualquiera. Y RkR^k es RR concatenada kk veces. Así, Σ∗1\Sigma^*\mathtt{1} es la expresión del principio, y (ΣΣ)∗(\Sigma\Sigma)^* o (Σ2)∗(\Sigma^2)^* describe las cadenas de longitud par.

Idea clave. Una expresión regular se arma con tres operaciones, unión, concatenación y estrella, a partir de los símbolos, ε\varepsilon y ∅\emptyset. Cada caso de la definición dice a la vez cómo se escribe la expresión y qué lenguaje describe. Por eso casi todo lo que se demuestra sobre expresiones regulares se demuestra con seis casos: tres bases y tres operaciones.

Precedencia y paréntesis

Con la definición tal cual, toda operación lleva sus paréntesis, y hasta las expresiones pequeñas se vuelven ilegibles. Como en la aritmética, se fija un orden y se quitan los paréntesis que ese orden hace innecesarios.

Precedencia. Primero la estrella, después la concatenación, al final la unión.

Es el mismo orden que el de la potencia, el producto y la suma: a+bc2a + bc^2 es a+(b(c2))a + (b(c^2)), y 0∪10∗\mathtt{0} \cup \mathtt{1}\mathtt{0}^* es 0∪(1(0∗))\mathtt{0} \cup (\mathtt{1}(\mathtt{0}^*)). La estrella se aplica solo a lo que tiene inmediatamente a su izquierda: un símbolo, o un grupo entre paréntesis.

El programa regex_tree lee una expresión y muestra cómo la entendió: con todos sus paréntesis, uno por cada operación, y como árbol, con la última operación que se aplica en la raíz.

$ build/regex_tree '0|10*' '(0|1)0*' '0|(10)*'
expresión:           0|10*
con sus paréntesis:  (0|(1(0*)))
nodos del árbol:     6
unión
    0
    concatenación
        1
        estrella
            0

expresión:           (0|1)0*
con sus paréntesis:  ((0|1)(0*))
nodos del árbol:     6
concatenación
    unión
        0
        1
    estrella
        0

expresión:           0|(10)*
con sus paréntesis:  (0|((10)*))
nodos del árbol:     6
unión
    0
    estrella
        concatenación
            1
            0
Los árboles de tres expresiones, uno al lado del otro, cada uno con su expresión arriba y debajo la misma expresión con todos sus paréntesis. El de 0 ∪ 10*, que es (0 ∪ (1(0*))): la raíz es una unión; su hijo izquierdo es la hoja 0 y el derecho una concatenación, que tiene a la izquierda la hoja 1 y a la derecha una estrella sobre la hoja 0. El de (0 ∪ 1)0*, que es ((0 ∪ 1)(0*)): la raíz es una concatenación; a la izquierda una unión de las hojas 0 y 1, y a la derecha una estrella sobre la hoja 0. El de 0 ∪ (10)*, que es (0 ∪ ((10)*)): la raíz es una unión; a la izquierda la hoja 0 y a la derecha una estrella, que tiene debajo una concatenación de las hojas 1 y 0. Cada árbol tiene tres hojas y tres operacionesLos árboles de tres expresiones, uno al lado del otro, cada uno con su expresión arriba y debajo la misma expresión con todos sus paréntesis. El de 0 ∪ 10*, que es (0 ∪ (1(0*))): la raíz es una unión; su hijo izquierdo es la hoja 0 y el derecho una concatenación, que tiene a la izquierda la hoja 1 y a la derecha una estrella sobre la hoja 0. El de (0 ∪ 1)0*, que es ((0 ∪ 1)(0*)): la raíz es una concatenación; a la izquierda una unión de las hojas 0 y 1, y a la derecha una estrella sobre la hoja 0. El de 0 ∪ (10)*, que es (0 ∪ ((10)*)): la raíz es una unión; a la izquierda la hoja 0 y a la derecha una estrella, que tiene debajo una concatenación de las hojas 1 y 0. Cada árbol tiene tres hojas y tres operaciones
Los mismos símbolos en el mismo orden y tres árboles distintos. La raíz es la última operación que se aplica, y lo que liga más fuerte queda más abajo.

Las tres expresiones tienen los mismos símbolos en el mismo orden, y solo cambian los paréntesis. Describen tres lenguajes distintos:

  • 0∪10∗\mathtt{0} \cup \mathtt{1}\mathtt{0}^*: la cadena 0\mathtt{0}, o un 1\mathtt{1} seguido de ceros. Es {0,1,10,100,…}\{\mathtt{0}, \mathtt{1}, \mathtt{10}, \mathtt{100}, \ldots\}.
  • (0∪1)0∗(\mathtt{0} \cup \mathtt{1})\mathtt{0}^*: un símbolo cualquiera seguido de ceros. Tiene además a 00\mathtt{00}, 000\mathtt{000}, …
  • 0∪(10)∗\mathtt{0} \cup (\mathtt{10})^*: la cadena 0\mathtt{0}, o repeticiones de 10\mathtt{10}. Tiene a ε\varepsilon y a 1010\mathtt{1010}, y no a 1\mathtt{1}.

El árbol es la forma en que conviene pensar una expresión, y es la forma en que la guardan los programas. Cada nodo es un caso de la definición: las hojas son los casos base y los nodos interiores son las operaciones. El tamaño de una expresión, que escribiremos ∣R∣|R|, es el número de nodos de su árbol. Las tres de arriba tienen tamaño 6: tres hojas y tres operaciones.

La unión y la concatenación son asociativas, así que R1∪R2∪R3R_1 \cup R_2 \cup R_3 y R1R2R3R_1R_2R_3 se escriben sin paréntesis. El árbol sí tiene que elegir cómo agrupar, y el parser del curso agrupa hacia la izquierda: ((R1∪R2)∪R3)((R_1 \cup R_2) \cup R_3). El lenguaje es el mismo con cualquiera de las dos agrupaciones.

Error común. Leer 01∗\mathtt{01}^* como “repeticiones de 01\mathtt{01}”. La estrella liga más que la concatenación: 01∗\mathtt{01}^* es 0(1∗)\mathtt{0}(\mathtt{1}^*), un cero seguido de unos. Las repeticiones de 01\mathtt{01} son (01)∗(\mathtt{01})^*. El mismo error con la unión: 0∪1∗\mathtt{0} \cup \mathtt{1}^* no es (0∪1)∗(\mathtt{0} \cup \mathtt{1})^*. Si dudan, pongan el paréntesis: uno de más no cambia el lenguaje, y uno de menos sí.

Cómo se escriben las expresiones en el código

Los programas de code/week-03 leen las expresiones en una línea de texto, con estas reglas:

En la teoría En el código Nota
un símbolo aa a Una letra o un dígito
R1∪R2R_1 \cup R_2 R1|R2 La barra vertical
R1R2R_1R_2 R1R2 No se escribe nada
R∗R^* R*
ε\varepsilon % También se acepta la letra ε
∅\emptyset @ También se acepta el signo ∅

Los paréntesis agrupan y los espacios se ignoran. Al imprimir, los programas escriben ε y ∅, y solo los paréntesis necesarios. En la terminal, la expresión va entre comillas simples, porque |, * y los paréntesis significan otra cosa para el shell.

Una expresión mal escrita no tiene árbol, y el parser dice dónde se quedó:

$ build/regex_tree '0|' '(0|1' '0+1'
0|
  error: posición 3: la expresión termina donde se esperaba un símbolo o un paréntesis

(0|1
  error: posición 5: falta cerrar un paréntesis

0+1
  error: posición 2: sobra +

La tercera no es un descuido: el + de las herramientas no está entre las tres operaciones de la definición. En errors/malformed.txt hay nueve expresiones mal formadas, y las pruebas comprueban que el parser rechaza cada una.

En C++. En regex.h, una expresión es un árbol de nodos Regex. Cada nodo tiene su caso, kind, que es uno de Empty, Epsilon, Symbol, Union, Concat y Star: los seis de la definición. Los hijos son std::shared_ptr<const Regex>, sin new ni delete, y como un árbol no cambia después de construido, dos expresiones pueden compartir un subárbol. El parser tiene una función por nivel de precedencia: parse_union llama a parse_concat, que llama a parse_star, que llama a parse_atom. Lo que liga más fuerte queda más abajo en la cadena de llamadas, y por eso más abajo en el árbol.

Leer expresiones

Leer una expresión es decir en palabras qué cadenas describe. El método es el de la definición: de adentro hacia afuera, o del árbol hacia la raíz. Tres ejemplos sobre Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\}.

Termina en 1

(0∪1)∗1(\mathtt{0} \cup \mathtt{1})^*\mathtt{1}

La raíz es una concatenación de dos partes. La primera, (0∪1)∗(\mathtt{0} \cup \mathtt{1})^*, es Σ∗\Sigma^*: cualquier cadena. La segunda es el símbolo 1\mathtt{1}. Una cadena cualquiera seguida de un 1\mathtt{1}: las cadenas que terminan en 1\mathtt{1}.

El programa regex_lang lista las cadenas más cortas del lenguaje de una expresión, en el orden de siempre.

$ build/regex_lang '(0|1)*1' 3
L((0|1)*1), hasta longitud 3:
  1 01 11 001 011 101 111
7 de 15 cadenas

De las 15 cadenas de longitud a lo sumo 3, hay 7 en el lenguaje: las que terminan en 1\mathtt{1}. La cadena vacía no está, porque no termina en nada.

Longitud par

(ΣΣ)∗=((0∪1)(0∪1))∗(\Sigma\Sigma)^* = ((\mathtt{0} \cup \mathtt{1})(\mathtt{0} \cup \mathtt{1}))^*

Adentro, ΣΣ\Sigma\Sigma describe las cuatro cadenas de dos símbolos. La estrella las repite cero o más veces: cadenas que se parten en trozos de longitud 2. Son las de longitud par, con la vacía incluida.

$ build/regex_lang '((0|1)(0|1))*' 4
L(((0|1)(0|1))*), hasta longitud 4:
  ε 00 01 10 11 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
21 de 31 cadenas

Son 1+4+16=211 + 4 + 16 = 21: todas las de longitud 0, 2 y 4.

Exactamente dos unos

0∗10∗10∗\mathtt{0}^*\mathtt{1}\mathtt{0}^*\mathtt{1}\mathtt{0}^*

Es una concatenación de cinco partes. Las partes fijas son los dos unos, y entre ellas, antes y después, hay ceros en cualquier cantidad. Las cadenas con exactamente dos unos.

$ build/regex_lang '0*10*10*' 4
L(0*10*10*), hasta longitud 4:
  11 011 101 110 0011 0101 0110 1001 1010 1100
10 de 31 cadenas

En cada longitud nn hay tantas como maneras de elegir las dos posiciones de los unos: 1, 3 y 6 para n=2n = 2, 3 y 4.

Para leer una expresión con estrellas, una buena pregunta es cómo se parte una cadena. La cadena 0110\mathtt{0110} está en el lenguaje porque se parte en 0⋅1⋅ε⋅1⋅0\mathtt{0} \cdot \mathtt{1} \cdot \varepsilon \cdot \mathtt{1} \cdot \mathtt{0}, una parte por cada factor de la expresión, y cada parte está en el lenguaje de su factor. Que una cadena esté en L(R)L(R) quiere decir que existe alguna manera de partirla que funcione. Puede haber varias, y basta una. Es el mismo “existe” de la aceptación de un NFA, y no es casualidad.

Escribir expresiones

Escribir es más difícil que leer, igual que diseñar un autómata es más difícil que seguirlo. No hay un método que siempre funcione, pero sí una pregunta que ordena el trabajo: ¿cómo se arma una cadena del lenguaje, pieza por pieza? Un autómata se diseña pensando qué recordar. Una expresión se diseña pensando en qué trozos se parte una cadena.

Número par de ceros

Lenguaje. A={ w∈{0,1}∗:w tiene un nuˊmero par de ceros }A = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : w \text{ tiene un número par de ceros} \,\}.

Los unos no importan: pueden estar en cualquier parte. Los ceros tienen que venir de dos en dos. Una cadena de AA se parte así: primero unos, y después varios bloques, cada uno con exactamente dos ceros y los unos que los acompañan.

1∗(01∗01∗)∗\mathtt{1}^*(\mathtt{0}\mathtt{1}^*\mathtt{0}\mathtt{1}^*)^*

Cada bloque 01∗01∗\mathtt{0}\mathtt{1}^*\mathtt{0}\mathtt{1}^* empieza en un cero impar (el primero, el tercero…), llega hasta el cero par siguiente y se lleva los unos que vienen después. Por ejemplo, 1101011\mathtt{1101011} se parte en 11\mathtt{11}, que son los unos del principio, y el bloque 01011\mathtt{01011}.

$ build/regex_lang '1*(01*01*)*' 3
L(1*(01*01*)*), hasta longitud 3:
  ε 1 00 11 001 010 100 111
8 de 15 cadenas

Hay otra manera de partir las mismas cadenas: en trozos que son un 1\mathtt{1} suelto, o un par de ceros con unos en medio. Eso da (1∪01∗0)∗(\mathtt{1} \cup \mathtt{0}\mathtt{1}^*\mathtt{0})^*, que es más corta. Las dos describen AA. El programa regex_diff las compara con todas las cadenas cortas:

$ build/regex_diff '1*(01*01*)*' '(1|01*0)*' 10
R1 = 1*(01*01*)*
R2 = (1|01*0)*
2047 cadenas de longitud a lo sumo 10
solo en R1: 0
solo en R2: 0
sin diferencias hasta esa longitud

Que no haya diferencias hasta longitud 10 no es una demostración: es una prueba, en el sentido de los programas. Sirve para encontrar errores, y encuentra casi todos, porque una expresión equivocada suele fallar con alguna cadena corta.

Sin 11

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

Aquí la condición es negativa, y las expresiones regulares no tienen un “no”. Hay que decir en positivo cómo es una cadena sin 11\mathtt{11}: todo 1\mathtt{1} va seguido de un 0\mathtt{0}, salvo que sea el último símbolo. Entonces la cadena se parte en bloques 0\mathtt{0} y 10\mathtt{10}, y al final puede sobrar un 1\mathtt{1}:

(0∪10)∗(ε∪1)(\mathtt{0} \cup \mathtt{10})^*(\varepsilon \cup \mathtt{1})
$ build/regex_lang '(0|10)*(%|1)' 3
L((0|10)*(ε|1)), hasta longitud 3:
  ε 0 1 00 01 10 000 001 010 100 101
11 de 15 cadenas

Faltan cuatro de las 15: 11\mathtt{11}, 011\mathtt{011}, 110\mathtt{110} y 111\mathtt{111}, que son justo las que contienen 11\mathtt{11}.

Esta vez vale la pena demostrarlo, porque la demostración muestra cómo se razona sobre una expresión: dos inclusiones, una por cada manera de equivocarse.

Afirmación. L((0∪10)∗(ε∪1))=BL((\mathtt{0} \cup \mathtt{10})^*(\varepsilon \cup \mathtt{1})) = B.

Demostración. Por doble inclusión.

La expresión no describe de más (⊆\subseteq). Sea ww una cadena del lenguaje de la expresión. Entonces w=uvw = uv, donde uu es una concatenación de bloques 0\mathtt{0} y 10\mathtt{10}, y vv es ε\varepsilon o 1\mathtt{1}. En uu, cada 1\mathtt{1} es el primer símbolo de un bloque 10\mathtt{10}, así que el símbolo que le sigue es un 0\mathtt{0}: en uu no hay 11\mathtt{11}, y si uu no es vacía, termina en 0\mathtt{0}. Si v=1v = \mathtt{1}, ese 1\mathtt{1} final va después de un 0\mathtt{0} o es toda la cadena. En ningún caso aparece 11\mathtt{11}, y w∈Bw \in B.

La expresión no describe de menos (⊇\supseteq). Sea ww una cadena sin 11\mathtt{11}. La partimos de izquierda a derecha. Si el símbolo que sigue es un 0\mathtt{0}, lo tomamos como un bloque 0\mathtt{0}. Si es un 1\mathtt{1} y no es el último símbolo, el siguiente tiene que ser un 0\mathtt{0}, porque ww no contiene 11\mathtt{11}: tomamos los dos como un bloque 10\mathtt{10}. Si es un 1\mathtt{1} y es el último, queda como la parte final. Así toda la cadena queda partida en bloques 0\mathtt{0} y 10\mathtt{10}, seguidos de ε\varepsilon o de 1\mathtt{1}, y por lo tanto está en el lenguaje de la expresión. ∎

Probar con cadenas de los dos lados

Una expresión puede estar mal de dos maneras, y las dos pasan desapercibidas si solo se prueba con las cadenas que uno tenía en mente.

Primer intento para BB: (0∪10)∗(\mathtt{0} \cup \mathtt{10})^*, sin la parte final. Todas las cadenas que describe están bien, sin 11\mathtt{11}. Pero describe de menos: ninguna de sus cadenas termina en 1\mathtt{1}.

$ build/regex_diff '(0|10)*' '(0|10)*(%|1)' 6
R1 = (0|10)*
R2 = (0|10)*(ε|1)
127 cadenas de longitud a lo sumo 6
solo en R1: 0
solo en R2: 20. Las más cortas: 1 01 001 101 0001 0101

Segundo intento, para arreglarlo: (0∪10)∗1∗(\mathtt{0} \cup \mathtt{10})^*\mathtt{1}^*, “y al final pueden venir unos”. Ahora están todas las cadenas de BB. Pero describe de más:

$ build/regex_diff '(0|10)*1*' '(0|10)*(%|1)' 6
R1 = (0|10)*1*
R2 = (0|10)*(ε|1)
127 cadenas de longitud a lo sumo 6
solo en R1: 26. Las más cortas: 11 011 111 0011 0111 1011
solo en R2: 0

La estrella final deja pasar a 11\mathtt{11}, que es justo lo que había que excluir.

Error común. Escribir una expresión que describe todo lo pedido y también cadenas que no debía, y comprobarla solo con ejemplos del lenguaje. Esa comprobación pasa siempre, por mala que sea la expresión: la expresión Σ∗\Sigma^* también describe todas las cadenas sin 11\mathtt{11}. Una expresión se prueba con cadenas de los dos lados: unas que deben estar y otras que no. Las de afuera se eligen cerca del borde: para “sin 11\mathtt{11}”, la propia 11\mathtt{11}, y cadenas que la tienen al principio, en medio y al final. Y siempre ε\varepsilon.

En la práctica. Es el error típico de un validador: un patrón para direcciones de correo que acepta todas las direcciones de prueba y también textos que no lo son. Las pruebas de un patrón llevan siempre dos listas, lo que debe coincidir y lo que no, y la segunda es la que encuentra los errores.

Identidades y trampas

Como las expresiones se combinan con operaciones, tienen su álgebra. Algunas igualdades valen para toda expresión RR, y conviene conocerlas porque permiten simplificar. En cada una, el signo igual dice que los dos lados describen el mismo lenguaje.

Identidad Por qué
R∪∅=RR \cup \emptyset = R Unir con el conjunto vacío no agrega cadenas
Rε=εR=RR\varepsilon = \varepsilon R = R Concatenar con la cadena vacía no cambia una cadena
R∅=∅R=∅R\emptyset = \emptyset R = \emptyset Para formar uvuv hay que elegir vv en ∅\emptyset, y no hay ninguna
∅∗=ε\emptyset^* = \varepsilon La única manera de partir una cadena en trozos de ∅\emptyset es en cero trozos
ε∗=ε\varepsilon^* = \varepsilon Repetir la cadena vacía da la cadena vacía
R∪R=RR \cup R = R Es una unión de conjuntos
(R∗)∗=R∗(R^*)^* = R^* Repetir repeticiones es repetir

Las cuatro primeras son las de la semana 1, escritas ahora con expresiones: ∅\emptyset hace de cero y ε\varepsilon hace de uno. Si la unión fuera la suma y la concatenación el producto, las tres primeras serían r+0=rr + 0 = r, r⋅1=rr \cdot 1 = r y r⋅0=0r \cdot 0 = 0.

La que sorprende es ∅∗=ε\emptyset^* = \varepsilon: la estrella de la expresión que no describe nada describe algo. Sale de la definición, porque A∗A^* siempre contiene a ε\varepsilon, sea AA lo que sea.

$ build/regex_lang '@*' 3 01
L(∅*), hasta longitud 3:
  ε
1 de 15 cadenas
$ build/regex_lang '0@' 3 01
L(0∅), hasta longitud 3:
  (ninguna)
0 de 15 cadenas
$ build/regex_lang '0|@' 3 01
L(0|∅), hasta longitud 3:
  0
1 de 15 cadenas
$ build/regex_lang '0%' 3 01
L(0ε), hasta longitud 3:
  0
1 de 15 cadenas

El tercer argumento de regex_lang es el alfabeto, que aquí hay que dar porque en @* no aparece ningún símbolo.

Las trampas son las mismas identidades con ε\varepsilon y ∅\emptyset cruzados. Son falsas:

  • R∪ε=RR \cup \varepsilon = R es falsa en general. Si R=0R = \mathtt{0}, la izquierda describe {ε,0}\{\varepsilon, \mathtt{0}\} y la derecha {0}\{\mathtt{0}\}. Unir con ε\varepsilon agrega la cadena vacía.
  • R∅=RR\emptyset = R es falsa. Si R=0R = \mathtt{0}, la izquierda describe ∅\emptyset. Concatenar con ∅\emptyset lo destruye todo.

Error común. Tratar a ε\varepsilon y a ∅\emptyset como “nada” en los dos casos. Para la unión, el que no hace nada es ∅\emptyset. Para la concatenación, el que no hace nada es ε\varepsilon. Cruzados, uno agrega una cadena y el otro borra el lenguaje entero.

Estas identidades no son solo una curiosidad. En la sesión B, un programa va a construir expresiones de forma mecánica, y sin ellas arrastraría términos como ∅∪0 ∅∗ 1\emptyset \cup \mathtt{0}\,\emptyset^*\,\mathtt{1} por todas partes. Las funciones simple_union, simple_concat y simple_star de regex.h aplican las cinco primeras filas de la tabla, y nada más.

Otras igualdades son menos evidentes. Por ejemplo, (0∪1)∗=(0∗1∗)∗(\mathtt{0} \cup \mathtt{1})^* = (\mathtt{0}^*\mathtt{1}^*)^*: los dos lados describen Σ∗\Sigma^*. No hay un procedimiento simple, como el de simplificar polinomios, que lleve una expresión a una forma única. Decidir si dos expresiones son equivalentes se puede, y el camino pasa por los autómatas: es uno de los frutos del teorema de esta semana.

De expresión regular a NFA: la construcción de Thompson

Ahora la primera de las dos direcciones: dada una expresión RR, construir un autómata que reconozca L(R)L(R).

La idea ya la tienen. La definición de expresión regular tiene seis casos. Para los tres casos base, el autómata se escribe a mano: son lenguajes de una cadena o de ninguna. Para los otros tres, la semana pasada vieron cómo combinar NFA con transiciones ε\varepsilon para obtener la unión, la concatenación y la estrella. Entonces basta recorrer el árbol de la expresión de las hojas a la raíz, armando en cada nodo el autómata de ese nodo con los autómatas de sus hijos.

La versión que usaremos es la de Ken Thompson, que la publicó en 1968 como parte de un algoritmo para buscar patrones en texto. Son las construcciones de cierre de la semana pasada con una disciplina adicional, que las hace más fáciles de programar y de contar.

La disciplina. Cada pieza tiene un solo estado inicial y un solo estado de aceptación, distintos entre sí. Al combinar piezas solo se agregan estados nuevos y transiciones ε\varepsilon: nunca se toca lo que hay dentro de una pieza ya construida.

Con una sola entrada y una sola salida, una pieza se puede tratar como una caja: para conectarla no hace falta saber qué tiene adentro.

Las seis piezas

Llamaremos ss a la entrada de una pieza y ff a su salida, que es su único estado de aceptación.

Las seis piezas de la construcción de Thompson. Arriba, los tres casos base, cada uno con dos estados, s con la flecha de inicio y f con doble círculo: para un símbolo a, una flecha de s a f con a; para ε, una flecha de s a f con ε; para ∅, los dos estados sin ninguna flecha. En el medio, a la izquierda, la unión de R₁ y R₂: las piezas de R₁ y de R₂ son dos cajas punteadas, una encima de la otra, con sus entradas s₁ y s₂ y sus salidas f₁ y f₂; un estado nuevo s tiene flechas ε hacia s₁ y hacia s₂, y de f₁ y de f₂ salen flechas ε hacia un estado nuevo f, que es el único de aceptación. A la derecha, la concatenación: las dos cajas en fila, la flecha de inicio entra a s₁, una flecha ε va de f₁ a s₂, y f₂ es el estado de aceptación; no hay estados nuevos. Abajo, la estrella de R₁: un estado nuevo s con una flecha ε a s₁, una flecha ε de f₁ a un estado nuevo f de aceptación, una flecha ε que vuelve de f₁ a s₁, rotulada otra vuelta, y una flecha ε que va directo de s a f por fuera de la caja, rotulada cero repeticiones. Los estados nuevos de la unión y de la estrella están en color oro, y las flechas ε en un tono más apagado que las de símboloLas seis piezas de la construcción de Thompson. Arriba, los tres casos base, cada uno con dos estados, s con la flecha de inicio y f con doble círculo: para un símbolo a, una flecha de s a f con a; para ε, una flecha de s a f con ε; para ∅, los dos estados sin ninguna flecha. En el medio, a la izquierda, la unión de R₁ y R₂: las piezas de R₁ y de R₂ son dos cajas punteadas, una encima de la otra, con sus entradas s₁ y s₂ y sus salidas f₁ y f₂; un estado nuevo s tiene flechas ε hacia s₁ y hacia s₂, y de f₁ y de f₂ salen flechas ε hacia un estado nuevo f, que es el único de aceptación. A la derecha, la concatenación: las dos cajas en fila, la flecha de inicio entra a s₁, una flecha ε va de f₁ a s₂, y f₂ es el estado de aceptación; no hay estados nuevos. Abajo, la estrella de R₁: un estado nuevo s con una flecha ε a s₁, una flecha ε de f₁ a un estado nuevo f de aceptación, una flecha ε que vuelve de f₁ a s₁, rotulada otra vuelta, y una flecha ε que va directo de s a f por fuera de la caja, rotulada cero repeticiones. Los estados nuevos de la unión y de la estrella están en color oro, y las flechas ε en un tono más apagado que las de símbolo
Las seis piezas, una por cada caso de la definición. Cada una tiene una sola entrada y una sola salida, y las operaciones solo agregan estados nuevos y flechas ε alrededor de las piezas ya construidas.

Los casos base. Tres piezas de dos estados.

Para un símbolo aa, la única manera de ir de ss a ff es leyendo aa. Para ε\varepsilon, sin leer nada. Para ∅\emptyset no hay ninguna manera, y el autómata no acepta nada.

Unión. Dadas la pieza de R1R_1, con entrada s1s_1 y salida f1f_1, y la de R2R_2, con s2s_2 y f2f_2, se agregan una entrada nueva ss y una salida nueva ff, con cuatro transiciones ε\varepsilon: dos de ss a las entradas s1s_1 y s2s_2, y dos de las salidas f1f_1 y f2f_2 a ff.

Desde ss, el autómata adivina cuál de las dos piezas va a recorrer. Al salir de cualquiera de las dos llega a ff.

Concatenación. No se agrega ningún estado: una transición ε\varepsilon une la salida de la primera pieza con la entrada de la segunda. La entrada del conjunto es s1s_1 y la salida es f2f_2.

Estrella. Una entrada y una salida nuevas, y cuatro transiciones ε\varepsilon: de ss a s1s_1, de f1f_1 a ff, de f1f_1 de vuelta a s1s_1, y de ss directo a ff.

Desde ss se puede ir directo a ff, sin recorrer la pieza: cero repeticiones. O entrar a la pieza, y al llegar a f1f_1 elegir entre volver a s1s_1, para dar otra vuelta, y salir a ff.

La estrella es la operación delicada, como vieron la semana pasada: marcar el estado inicial de la pieza como de aceptación, para aceptar ε\varepsilon, puede hacer que el autómata acepte cadenas que no debía. Aquí el problema no aparece, porque la entrada y la salida nuevas no forman parte de la pieza: nada de lo que pasa adentro puede terminar en ff sin haber llegado antes a f1f_1.

En el formato .nfa, las piezas más pequeñas se ven así. El programa thompson recibe una expresión y escribe su autómata:

$ build/thompson '0|1'
# NFA de Thompson de 0|1
states: q0 q1 q2 q3 q4 q5
alphabet: 0 1
start: q0
accept: q5
delta:
q0 eps q1 q3
q1 0 q2
q2 eps q5
q3 1 q4
q4 eps q5

La entrada nueva es q0 y la salida nueva es q5. La pieza del 0\mathtt{0} es q1 y q2, y la del 1\mathtt{1} es q3 y q4.

$ build/thompson '0*'
# NFA de Thompson de 0*
states: q0 q1 q2 q3
alphabet: 0
start: q0
accept: q3
delta:
q0 eps q1 q3
q1 0 q2
q2 eps q1 q3

Aquí la pieza del 0\mathtt{0} es q1 y q2. Desde q0 se entra a la pieza o se salta a q3. Desde q2, la salida de la pieza, se vuelve a q1 o se sale a q3.

Un ejemplo completo

Construyamos el autómata de (0∪1)∗1(\mathtt{0} \cup \mathtt{1})^*\mathtt{1}, la expresión de las cadenas que terminan en 1\mathtt{1}. Su árbol tiene 6 nodos: una concatenación en la raíz, con la estrella de una unión a la izquierda y un 1\mathtt{1} a la derecha.

$ build/thompson '(0|1)*1'
# NFA de Thompson de (0|1)*1
states: q0 q1 q2 q3 q4 q5 q6 q7 q8 q9
alphabet: 0 1
start: q0
accept: q9
delta:
q0 eps q1 q7
q1 eps q2 q4
q2 0 q3
q3 eps q6
q4 1 q5
q5 eps q6
q6 eps q1 q7
q7 eps q8
q8 1 q9

El programa numera los estados en el orden en que los crea. Cada grupo de estados es una pieza:

Nodo del árbol Entrada Salida Estados nuevos
0\mathtt{0} q2q_2 q3q_3 q2q_2, q3q_3
1\mathtt{1}, el de la unión q4q_4 q5q_5 q4q_4, q5q_5
0∪1\mathtt{0} \cup \mathtt{1} q1q_1 q6q_6 q1q_1, q6q_6
(0∪1)∗(\mathtt{0} \cup \mathtt{1})^* q0q_0 q7q_7 q0q_0, q7q_7
1\mathtt{1}, el final q8q_8 q9q_9 q8q_8, q9q_9
la concatenación q0q_0 q9q_9 ninguno

Como diagrama, armado en el orden de la tabla:

Animación de la construcción de Thompson para (0 ∪ 1)*1, en seis pasos. Arriba está la expresión, con la parte que corresponde a cada paso resaltada; en el medio se va armando el autómata. Paso 1, la hoja 0: los estados q₂ y q₃ con una flecha con 0 entre ellos. Paso 2, la hoja 1 de la unión: debajo, los estados q₄ y q₅ con una flecha con 1. Paso 3, la unión: aparecen q₁ a la izquierda y q₆ a la derecha, con flechas ε de q₁ a q₂ y a q₄, y de q₃ y de q₅ a q₆. Paso 4, la estrella: aparecen q₀ antes de q₁ y q₇ después de q₆, con flechas ε de q₀ a q₁, de q₆ a q₇, de q₆ de vuelta a q₁ y, por encima de todo, de q₀ a q₇. Paso 5, el 1 final: a la derecha, los estados q₈ y q₉ con una flecha con 1. Paso 6, la concatenación: una flecha ε de q₇ a q₈ une las dos piezas. En cada paso, cada pieza tiene su flecha de inicio y su doble círculo; al final, la flecha de inicio entra a q₀ y el único estado de aceptación es q₉Animación de la construcción de Thompson para (0 ∪ 1)*1, en seis pasos. Arriba está la expresión, con la parte que corresponde a cada paso resaltada; en el medio se va armando el autómata. Paso 1, la hoja 0: los estados q₂ y q₃ con una flecha con 0 entre ellos. Paso 2, la hoja 1 de la unión: debajo, los estados q₄ y q₅ con una flecha con 1. Paso 3, la unión: aparecen q₁ a la izquierda y q₆ a la derecha, con flechas ε de q₁ a q₂ y a q₄, y de q₃ y de q₅ a q₆. Paso 4, la estrella: aparecen q₀ antes de q₁ y q₇ después de q₆, con flechas ε de q₀ a q₁, de q₆ a q₇, de q₆ de vuelta a q₁ y, por encima de todo, de q₀ a q₇. Paso 5, el 1 final: a la derecha, los estados q₈ y q₉ con una flecha con 1. Paso 6, la concatenación: una flecha ε de q₇ a q₈ une las dos piezas. En cada paso, cada pieza tiene su flecha de inicio y su doble círculo; al final, la flecha de inicio entra a q₀ y el único estado de aceptación es q₉
El autómata de (0 ∪ 1)*1 se arma de las hojas a la raíz: una pieza por nodo del árbol. El resultado es, flecha por flecha, el que imprime thompson.

La tabla de transiciones tiene una columna más que la de un DFA, la de ε\varepsilon, y en cada casilla hay un conjunto de estados. Las casillas vacías son ∅\emptyset: desde ahí, con ese símbolo, el camino muere.

δ\delta 0\mathtt{0} 1\mathtt{1} ε\varepsilon
q0q_0 {q1,q7}\{q_1, q_7\}
q1q_1 {q2,q4}\{q_2, q_4\}
q2q_2 {q3}\{q_3\}
q3q_3 {q6}\{q_6\}
q4q_4 {q5}\{q_5\}
q5q_5 {q6}\{q_6\}
q6q_6 {q1,q7}\{q_1, q_7\}
q7q_7 {q8}\{q_8\}
q8q_8 {q9}\{q_9\}
q9q_9

Este autómata está guardado en machines/ends_in_1.nfa. Para seguirlo con una cadena se lleva, como la semana pasada, el conjunto de estados activos: todos los estados en los que el autómata puede estar después de lo leído. Se empieza con la clausura ε\varepsilon del estado inicial. Con cada símbolo se avanza por las flechas de ese símbolo desde todos los activos, y se toma otra vez la clausura ε\varepsilon.

$ build/run_nfa machines/ends_in_1.nfa 011 010 ''
w = 011
  inicio  {q0, q1, q2, q4, q7, q8}
  lee 0   {q1, q2, q3, q4, q6, q7, q8}
  lee 1   {q1, q2, q4, q5, q6, q7, q8, q9}
  lee 1   {q1, q2, q4, q5, q6, q7, q8, q9}
  hay un estado de F entre los activos: acepta
w = 010
  inicio  {q0, q1, q2, q4, q7, q8}
  lee 0   {q1, q2, q3, q4, q6, q7, q8}
  lee 1   {q1, q2, q4, q5, q6, q7, q8, q9}
  lee 0   {q1, q2, q3, q4, q6, q7, q8}
  ningún estado activo está en F: rechaza
w = ε
  inicio  {q0, q1, q2, q4, q7, q8}
  ningún estado activo está en F: rechaza

Miren el conjunto inicial. Antes de leer nada, el autómata ya está en seis estados a la vez: en q2q_2 y q4q_4, listo para leer un símbolo de (0∪1)∗(\mathtt{0} \cup \mathtt{1})^*, y en q8q_8, listo para leer el 1\mathtt{1} final. No sabe cuál de los unos será el último, y no hace falta que lo sepa: sigue las dos posibilidades. Después de cada 1\mathtt{1}, el estado q9q_9 está entre los activos, que es la manera en que el autómata dice “si la cadena terminara aquí, la aceptaría”.

Idea clave. La construcción de Thompson copia la estructura de la expresión: una pieza por cada nodo del árbol, con una entrada y una salida. Las transiciones ε\varepsilon son el pegamento. El autómata que sale no es pequeño ni elegante, pero se construye sin pensar, y eso es justo lo que necesita un programa.

Por qué funciona

Teorema. Para toda expresión regular RR hay un NFA que reconoce L(R)L(R).

Demostración. Por construcción, y la construcción es la de Thompson. Demostramos algo un poco más preciso, que es lo que permite combinar piezas.

Afirmación. La pieza de RR, con entrada ss y salida ff, cumple para toda cadena ww: hay un camino de ss a ff que deletrea ww si y solo si w∈L(R)w \in L(R).

Un camino deletrea ww si, al leer en orden las etiquetas de sus flechas y saltarse las ε\varepsilon, sale ww. Como ss es el estado inicial y ff el único de aceptación, la afirmación dice exactamente que el autómata acepta ww si y solo si w∈L(R)w \in L(R).

La demostración es por inducción sobre la estructura de RR: se demuestra para los casos base y, para cada operación, se supone cierta para las expresiones más pequeñas R1R_1 y R2R_2. Es la inducción sobre el tamaño del árbol.

Casos base. En la pieza de un símbolo aa hay un solo camino de ss a ff, y deletrea aa: la afirmación vale porque L(a)={a}L(a) = \{a\}. En la de ε\varepsilon hay un solo camino, que deletrea ε\varepsilon. En la de ∅\emptyset no hay ninguno, y L(∅)L(\emptyset) no tiene cadenas.

Unión. Supongamos la afirmación para las piezas de R1R_1 y de R2R_2.

Si w∈L(R1∪R2)w \in L(R_1 \cup R_2), entonces ww está en L(R1)L(R_1) o en L(R2)L(R_2). Digamos que en L(R1)L(R_1). Por hipótesis hay un camino de s1s_1 a f1f_1 que deletrea ww. Con la flecha ε\varepsilon de ss a s1s_1 delante y la de f1f_1 a ff detrás, es un camino de ss a ff que deletrea ww.

Al revés, tomemos un camino de ss a ff que deletrea ww. Su primera flecha sale de ss, y de ss solo salen las dos ε\varepsilon hacia s1s_1 y s2s_2. Digamos que va a s1s_1. Desde ahí el camino está dentro de la pieza de R1R_1, y la única flecha que sale de esa pieza es la ε\varepsilon de f1f_1 a ff. De ff no sale ninguna flecha, así que el camino termina ahí. El camino es entonces: una ε\varepsilon, un camino de s1s_1 a f1f_1 dentro de la pieza de R1R_1, y otra ε\varepsilon. El tramo del medio deletrea ww, y por hipótesis w∈L(R1)w \in L(R_1).

Concatenación. Si w∈L(R1R2)w \in L(R_1R_2), entonces w=uvw = uv con u∈L(R1)u \in L(R_1) y v∈L(R2)v \in L(R_2). Un camino de s1s_1 a f1f_1 que deletrea uu, la flecha ε\varepsilon de f1f_1 a s2s_2, y un camino de s2s_2 a f2f_2 que deletrea vv forman un camino de s1s_1 a f2f_2 que deletrea uvuv.

Al revés, un camino de s1s_1 a f2f_2 tiene que pasar de la primera pieza a la segunda, y la única flecha que las une es la ε\varepsilon de f1f_1 a s2s_2. No hay flechas de vuelta, así que la usa exactamente una vez. Lo que hay antes es un camino de s1s_1 a f1f_1 dentro de la primera pieza, que deletrea alguna u∈L(R1)u \in L(R_1). Lo que hay después es un camino de s2s_2 a f2f_2 dentro de la segunda, que deletrea alguna v∈L(R2)v \in L(R_2). Y w=uvw = uv.

Estrella. Si w∈L(R1∗)w \in L(R_1^*), hay dos casos. Si w=εw = \varepsilon, la flecha ε\varepsilon de ss a ff es un camino que la deletrea. Si no, w=u1u2⋯ukw = u_1u_2 \cdots u_k con k≥1k \geq 1 y cada ui∈L(R1)u_i \in L(R_1). Por hipótesis, para cada uiu_i hay un camino de s1s_1 a f1f_1 que lo deletrea. El camino buscado entra con la ε\varepsilon de ss a s1s_1, recorre esos kk caminos unidos por la flecha ε\varepsilon de vuelta, de f1f_1 a s1s_1, y sale con la ε\varepsilon de f1f_1 a ff.

Al revés, tomemos un camino de ss a ff que deletrea ww. Si es la flecha directa, w=εw = \varepsilon, que está en L(R1∗)L(R_1^*). Si no, empieza con la ε\varepsilon de ss a s1s_1 y termina con la ε\varepsilon de f1f_1 a ff, porque a ff solo se llega desde ss y desde f1f_1. Entre una y otra, el camino solo puede usar flechas de la pieza de R1R_1 y la flecha de vuelta. Lo cortamos en cada uso de la flecha de vuelta. Cada trozo empieza en s1s_1, termina en f1f_1 y usa solo flechas de la pieza: por hipótesis deletrea una cadena de L(R1)L(R_1). Entonces ww es una concatenación de una o más cadenas de L(R1)L(R_1), y está en L(R1∗)L(R_1^*). ∎

La demostración tiene la misma forma que la definición y que el programa: seis casos. La función build_fragment de thompson.h es un switch con esos seis casos, y cada uno hace lo que dice su dibujo.

Cuántos estados tiene

Contemos. Cada caso base crea 2 estados. La unión y la estrella crean 2 cada una. La concatenación no crea ninguno. Entonces el número de estados es exactamente

2⋅(hojas+uniones+estrellas)≤2 ∣R∣.2 \cdot (\text{hojas} + \text{uniones} + \text{estrellas}) \leq 2\,|R|.

Para (0∪1)∗1(\mathtt{0} \cup \mathtt{1})^*\mathtt{1} son 3 hojas, 1 unión y 1 estrella: 2⋅5=102 \cdot 5 = 10 estados, los de arriba. Y las flechas también son pocas: de cada estado salen a lo sumo dos. En las seis piezas se ve que de un estado sale una flecha con un símbolo, o una o dos ε\varepsilon, o ninguna.

Idea clave. El NFA de Thompson tiene un número de estados y de flechas lineal en el tamaño de la expresión: a lo sumo 2 ∣R∣2\,|R| estados y 4 ∣R∣4\,|R| flechas. Pasar de la descripción a una máquina no determinista es barato. Lo caro, cuando hace falta, es el paso siguiente: la construcción de subconjuntos puede multiplicar los estados de forma exponencial.

Si se compara con lo que uno dibujaría a mano, sobran estados. Para las cadenas que terminan en 1\mathtt{1} basta un NFA de dos estados: uno con un ciclo para 0\mathtt{0} y 1\mathtt{1}, y una flecha con 1\mathtt{1} al de aceptación. Los ocho estados de más son el precio de no pensar. Hay construcciones que evitan las transiciones ε\varepsilon y dan autómatas más pequeños, pero ninguna es tan simple de programar ni de demostrar.

En C++. thompson.h agrega los estados a un Nfa con new_state, que les pone el siguiente nombre libre, y cada caso devuelve un Fragment: el nombre de la entrada y el de la salida. La concatenación son tres líneas: construir la primera pieza, construir la segunda, y agregar una transición ε\varepsilon entre ellas. El código construye las dos piezas en dos instrucciones separadas a propósito: si las dos llamadas fueran argumentos de una misma función, C++ no fija cuál se evalúa primero, y los estados podrían quedar numerados de otro modo en otra máquina.

Las abreviaturas de las herramientas

Las expresiones de grep, de un editor o de un lenguaje de programación tienen muchos más operadores que los tres de la definición. Casi todos son abreviaturas: se pueden reescribir con unión, concatenación y estrella, y por eso no agregan ningún lenguaje nuevo.

En las herramientas Significa Con las tres operaciones
R+ Una o más repeticiones RR∗RR^*
R? Opcional: cero o una vez R∪εR \cup \varepsilon
[abc] Uno de estos símbolos a∪b∪c\mathtt{a} \cup \mathtt{b} \cup \mathtt{c}
[a-z] Un símbolo del rango a∪b∪⋯∪z\mathtt{a} \cup \mathtt{b} \cup \cdots \cup \mathtt{z}
. Un símbolo cualquiera Σ\Sigma
R{3} Exactamente tres veces RRRRRR
R{2,3} Entre dos y tres veces RR(R∪ε)RR(R \cup \varepsilon)
R{2,} Dos veces o más RRR∗RRR^*

El argumento de que no agregan poder es siempre el mismo: una expresión con abreviaturas se traduce, operador por operador, a una expresión de la definición que describe el mismo lenguaje. Entonces todo lenguaje que se describe con abreviaturas se describe también sin ellas. La expresión de las fechas del principio es

DD/DD/DDDD,donde D=0∪1∪⋯∪9.DD\mathtt{/}DD\mathtt{/}DDDD, \qquad \text{donde } D = \mathtt{0} \cup \mathtt{1} \cup \cdots \cup \mathtt{9}.

Y los enteros sin ceros a la izquierda, que en una herramienta serían 0|[1-9][0-9]*, son 0∪(1∪⋯∪9)(0∪⋯∪9)∗\mathtt{0} \cup (\mathtt{1} \cup \cdots \cup \mathtt{9})(\mathtt{0} \cup \cdots \cup \mathtt{9})^*. Las pruebas de la semana comparan esa expresión, escrita entera, con una función que mira si la cadena es 0\mathtt{0} o empieza con un dígito distinto de cero.

Que no agreguen poder no quiere decir que no sirvan. Sirven para escribir menos, a veces muchísimo menos: [a-z]{1000} son once caracteres, y la expresión sin abreviaturas tiene 1000 copias de una unión de 26 símbolos. Las llaves pueden hacer que la expresión traducida, y con ella su autómata, sea exponencialmente más grande que lo que se escribió, porque el número va escrito en decimal.

Hay dos diferencias más entre las herramientas y la teoría, que no son abreviaturas sino convenciones.

  • Buscar frente a coincidir. L(R)L(R) es el conjunto de las cadenas que RR describe completas. grep, por defecto, imprime una línea si el patrón aparece en alguna parte de ella. En nuestros términos, grep R decide si la línea está en L(Σ∗R Σ∗)L(\Sigma^* R\, \Sigma^*). Con la opción -x, o con las anclas ^ y $ al principio y al final del patrón, pide la línea completa.
  • El alfabeto. Para la teoría es un conjunto pequeño que se fija de antemano. Para una herramienta son todos los caracteres, y hace falta una manera de escribir como símbolo un carácter que también es operador: \*, \(, \|.
$ printf '1\n0110\n\n0111\n' | grep -xE '(0|1)*1'
1
0111

Con -x, grep hace lo mismo que nuestra definición: de las cuatro líneas, imprime las dos que terminan en 1\mathtt{1}. La tercera línea es la cadena vacía. La opción -E elige la sintaxis en la que |, ( y ) son operadores sin necesidad de barra invertida.

En la práctica. No todo lo que una herramienta llama regex es una expresión regular en el sentido de este capítulo. Algunas agregan operadores que no son abreviaturas, y con ellos describen lenguajes que ningún autómata finito reconoce. El más conocido es la referencia hacia atrás, que aparece al final de la sesión B.

La dirección difícil

La sesión A mostró que toda expresión regular tiene su autómata. Como todo NFA se convierte en un DFA, el lenguaje de una expresión regular es siempre regular. Falta la otra dirección: ¿todo lenguaje regular tiene una expresión?

No es evidente. Las expresiones no tienen complemento ni intersección, y los lenguajes regulares son cerrados bajo los dos. El lenguaje de las cadenas sin 11\mathtt{11} nos costó dos intentos fallidos, y su DFA sale casi sin pensar: es el complemento de “contiene 11\mathtt{11}”. ¿Y si hubiera lenguajes regulares que ninguna expresión alcanza a describir?

Intentemos leer la expresión directamente de un diagrama, con el autómata de la paridad de la semana 1, que acepta las cadenas con un número par de unos. Está en machines/even_ones.dfa.

δ\delta 0\mathtt{0} 1\mathtt{1}
par\mathit{par} (inicial, de aceptación) par\mathit{par} impar\mathit{impar}
impar\mathit{impar} impar\mathit{impar} par\mathit{par}

Una cadena aceptada es un paseo que sale de par\mathit{par} y vuelve a par\mathit{par}. Ese paseo se parte en vueltas: cada vuelta sale de par\mathit{par} y regresa por primera vez. Hay dos tipos de vuelta. La corta es el ciclo con 0\mathtt{0}. La larga va a impar\mathit{impar} con un 1\mathtt{1}, se queda ahí dando vueltas con ceros, y regresa con otro 1\mathtt{1}: es 10∗1\mathtt{1}\mathtt{0}^*\mathtt{1}. Una cadena aceptada es cualquier secuencia de vueltas:

(0∪10∗1)∗(\mathtt{0} \cup \mathtt{1}\mathtt{0}^*\mathtt{1})^*

Funcionó, y lo que hicimos tiene nombre. Para describir las vueltas largas nos deshicimos del estado impar\mathit{impar}: resumimos todo lo que pasa mientras el autómata está ahí en una sola expresión, 10∗1\mathtt{1}\mathtt{0}^*\mathtt{1}, que va de par\mathit{par} a par\mathit{par}. El estado desapareció y, a cambio, una flecha pasó a llevar una expresión en vez de un símbolo.

Esa es la idea de toda la sesión. Con dos estados se hace de memoria. Con veinte hay que hacerlo con método, y el método necesita un tipo de autómata en el que una flecha pueda llevar una expresión.

Autómatas con expresiones en las flechas

Definición. Un autómata finito no determinista generalizado (generalized nondeterministic finite automaton), o GNFA, es un autómata en el que cada flecha lleva una expresión regular, y que cumple tres condiciones de forma:

  1. Tiene un estado inicial qiniq_{\text{ini}} al que no entra ninguna flecha.
  2. Tiene un único estado de aceptación qfinq_{\text{fin}}, distinto del inicial, del que no sale ninguna flecha.
  3. Entre cada par de estados hay exactamente una flecha en cada sentido, y cada estado tiene una flecha a sí mismo, salvo lo que prohíben las condiciones 1 y 2.

La expresión de la flecha que va de qiq_i a qjq_j se escribe RijR_{ij}. La condición 3 parece exigir muchísimas flechas, pero una flecha puede llevar la expresión ∅\emptyset, y una flecha con ∅\emptyset no se puede usar nunca. Entonces la condición se cumple sola con un convenio: una flecha que no está dibujada lleva ∅\emptyset.

Un GNFA lee la entrada por trozos. Para pasar de qiq_i a qjq_j consume de la entrada un trozo entero, que tiene que estar en L(Rij)L(R_{ij}). Con precisión: el GNFA acepta ww si ww se puede partir en trozos w=w1w2⋯wkw = w_1w_2 \cdots w_k, donde cada wiw_i es una cadena, y hay una secuencia de estados p0,p1,…,pkp_0, p_1, \ldots, p_k tal que:

  • p0=qinip_0 = q_{\text{ini}} y pk=qfinp_k = q_{\text{fin}};
  • para cada ii, el trozo wiw_i está en L(R)L(R), donde RR es la expresión de la flecha de pi−1p_{i-1} a pip_i.

Un trozo puede ser vacío, si la expresión de su flecha describe ε\varepsilon. Un NFA es el caso en el que todas las expresiones son un símbolo o ε\varepsilon.

Normalizar un DFA

Un DFA cualquiera no cumple las condiciones 1 y 2: su estado inicial puede tener flechas que entran, y puede tener varios estados de aceptación, con flechas que salen. Se arregla con dos estados nuevos.

  1. Un estado inicial nuevo, qiniq_{\text{ini}}, con una flecha ε\varepsilon al estado inicial del DFA.
  2. Un estado de aceptación nuevo, qfinq_{\text{fin}}, al que llega una flecha ε\varepsilon desde cada estado de aceptación del DFA. Los que eran de aceptación dejan de serlo.
  3. Si de un estado a otro hay varias flechas, con símbolos distintos, se juntan en una que lleva la unión de esos símbolos.

El programa eliminate empieza mostrando el GNFA de un DFA. Los estados nuevos se llaman ini y fin.

Autómata generalizado de machines/even_ones.dfa
  estados: ini par impar fin
  ini -> par :  ε
  par -> par :  0
  par -> impar :  1
  par -> fin :  ε
  impar -> par :  1
  impar -> impar :  0

El GNFA tiene dos estados más que el DFA. Las flechas que no aparecen en la lista, como la de ini a impar, llevan ∅\emptyset.

Afirmación. El GNFA de un DFA MM acepta las mismas cadenas que MM.

Demostración. En las dos direcciones.

Si MM acepta w=a1a2⋯anw = a_1a_2 \cdots a_n, su ejecución es r0,r1,…,rnr_0, r_1, \ldots, r_n con r0=q0r_0 = q_0 y rn∈Fr_n \in F. En el GNFA, la secuencia qini,r0,r1,…,rn,qfinq_{\text{ini}}, r_0, r_1, \ldots, r_n, q_{\text{fin}} con los trozos ε,a1,…,an,ε\varepsilon, a_1, \ldots, a_n, \varepsilon cumple la definición: la flecha de ri−1r_{i-1} a rir_i lleva la unión de los símbolos que hacen ese paso, y aia_i es uno de ellos.

Al revés, supongamos que el GNFA acepta ww con cierta secuencia de estados. De qiniq_{\text{ini}} sale una sola flecha que no es ∅\emptyset, la ε\varepsilon hacia q0q_0: el primer trozo es ε\varepsilon y el segundo estado es q0q_0. A qfinq_{\text{fin}} solo llegan flechas ε\varepsilon desde estados de FF: el último trozo es ε\varepsilon y el penúltimo estado está en FF. Todas las demás flechas llevan una unión de símbolos, así que cada trozo intermedio es un solo símbolo aa, y va de un estado pp a δ(p,a)\delta(p, a). Los estados intermedios son entonces la ejecución de MM con ww, que termina en FF. ∎

Eliminar un estado

Ahora el paso central. Tenemos un GNFA con al menos tres estados y queremos otro con un estado menos que acepte lo mismo. Elegimos un estado qkq_k que no sea qiniq_{\text{ini}} ni qfinq_{\text{fin}}, y lo quitamos. Para que no se pierda ninguna cadena hay que reparar las flechas: todo camino que pasaba por qkq_k tiene que seguir existiendo sin él.

Un camino que pasa por qkq_k entra desde algún estado qiq_i, da cero o más vueltas en el ciclo de qkq_k sobre sí mismo, y sale hacia algún estado qjq_j. Lo que lee en ese tramo es un trozo de RikR_{ik}, después cero o más trozos de RkkR_{kk}, y después un trozo de RkjR_{kj}. Eso es una concatenación con una estrella en medio. La flecha directa de qiq_i a qjq_j pasa a ofrecer las dos posibilidades, la que ya tenía y el desvío:

Rij′=Rij∪Rik (Rkk)∗ RkjR_{ij}' = R_{ij} \cup R_{ik}\,(R_{kk})^*\,R_{kj}
Dos dibujos, antes y después de eliminar el estado q_k. Antes: tres estados, q_i a la izquierda, q_j a la derecha y q_k arriba, entre los dos. De q_i sale una flecha hacia q_k con la expresión R_ik, rotulada entra; q_k tiene un bucle con R_kk, rotulado da vueltas; de q_k sale una flecha hacia q_j con R_kj, rotulada sale. Esas tres flechas y q_k están resaltados. Abajo, la flecha directa de q_i a q_j, con R_ij. Después: quedan q_i y q_j, con una sola flecha de q_i a q_j que lleva R_ij ∪ R_ik (R_kk)* R_kj. Debajo de la expresión, R_ij está señalada como lo que la flecha ya tenía, y R_ik (R_kk)* R_kj como el desvío por q_k: entra, da cero o más vueltas en su ciclo, y saleDos dibujos, antes y después de eliminar el estado q_k. Antes: tres estados, q_i a la izquierda, q_j a la derecha y q_k arriba, entre los dos. De q_i sale una flecha hacia q_k con la expresión R_ik, rotulada entra; q_k tiene un bucle con R_kk, rotulado da vueltas; de q_k sale una flecha hacia q_j con R_kj, rotulada sale. Esas tres flechas y q_k están resaltados. Abajo, la flecha directa de q_i a q_j, con R_ij. Después: quedan q_i y q_j, con una sola flecha de q_i a q_j que lleva R_ij ∪ R_ik (R_kk)* R_kj. Debajo de la expresión, R_ij está señalada como lo que la flecha ya tenía, y R_ik (R_kk)* R_kj como el desvío por q_k: entra, da cero o más vueltas en su ciclo, y sale
Al eliminar q_k, la flecha de q_i a q_j ofrece las dos posibilidades: la que ya tenía y el desvío por el estado que desaparece.

La regla. Para eliminar qkq_k, se cambia la expresión de cada pareja (qi,qj)(q_i, q_j) de los estados que quedan por Rij∪Rik(Rkk)∗RkjR_{ij} \cup R_{ik}(R_{kk})^*R_{kj}. Después se borra qkq_k con todas sus flechas.

“Cada pareja” incluye las parejas con i=ji = j: el ciclo de un estado sobre sí mismo también se repara. E incluye las dos direcciones, (qi,qj)(q_i, q_j) y (qj,qi)(q_j, q_i), que son parejas distintas. Solo se excluyen las que las condiciones de forma prohíben: qfinq_{\text{fin}} no hace de qiq_i y qiniq_{\text{ini}} no hace de qjq_j.

En la práctica, casi todas las parejas se resuelven solas gracias a las identidades de la sesión A. Si no hay flecha de qiq_i a qkq_k, entonces Rik=∅R_{ik} = \emptyset, el desvío es ∅(Rkk)∗Rkj=∅\emptyset(R_{kk})^*R_{kj} = \emptyset, y la flecha queda como estaba, porque Rij∪∅=RijR_{ij} \cup \emptyset = R_{ij}. Solo cambian las parejas en las que qiq_i tiene una flecha hacia qkq_k y qkq_k tiene una flecha hacia qjq_j. Y si qkq_k no tiene ciclo, Rkk=∅R_{kk} = \emptyset, y el factor del medio es ∅∗=ε\emptyset^* = \varepsilon, que desaparece de la concatenación.

Método para hacerlo a mano sin olvidar nada:

  1. Listar los estados que entran a qkq_k: los qi≠qkq_i \neq q_k con flecha hacia qkq_k.
  2. Listar los estados que salen de qkq_k: los qj≠qkq_j \neq q_k a los que qkq_k tiene flecha.
  3. Anotar el ciclo RkkR_{kk}, si lo hay.
  4. Por cada combinación de uno que entra y uno que sale, calcular Rik(Rkk)∗RkjR_{ik}(R_{kk})^*R_{kj} y unirlo a la flecha de qiq_i a qjq_j. Si hay mm que entran y nn que salen, son m⋅nm \cdot n parejas. Un mismo estado puede estar en las dos listas, y entonces la pareja (qi,qi)(q_i, q_i) repara su ciclo.

El ejemplo de dos estados

Eliminemos impar\mathit{impar} en el GNFA de la paridad.

  1. Entra: par\mathit{par}, con 1\mathtt{1}.
  2. Sale: par\mathit{par}, con 1\mathtt{1}.
  3. Ciclo: 0\mathtt{0}.
  4. Una sola pareja, (par,par)(\mathit{par}, \mathit{par}):
Rpar,par′=0∪1 (0)∗ 1R_{\mathit{par},\mathit{par}}' = \mathtt{0} \cup \mathtt{1}\,(\mathtt{0})^*\,\mathtt{1}

Queda un GNFA de tres estados, qiniq_{\text{ini}}, par\mathit{par} y qfinq_{\text{fin}}. Ahora eliminamos par\mathit{par}. Entra qiniq_{\text{ini}} con ε\varepsilon, sale qfinq_{\text{fin}} con ε\varepsilon, y el ciclo es el que acabamos de calcular. No había flecha de qiniq_{\text{ini}} a qfinq_{\text{fin}}:

Rini,fin′=∅∪ε (0∪10∗1)∗ ε=(0∪10∗1)∗R_{\text{ini},\text{fin}}' = \emptyset \cup \varepsilon\,(\mathtt{0} \cup \mathtt{1}\mathtt{0}^*\mathtt{1})^*\,\varepsilon = (\mathtt{0} \cup \mathtt{1}\mathtt{0}^*\mathtt{1})^*

Quedan dos estados y una flecha. La expresión de esa flecha es la respuesta, y es la que habíamos leído del diagrama. El programa hace los mismos pasos:

$ build/eliminate machines/even_ones.dfa impar par
Autómata generalizado de machines/even_ones.dfa
  estados: ini par impar fin
  ini -> par :  ε
  par -> par :  0
  par -> impar :  1
  par -> fin :  ε
  impar -> par :  1
  impar -> impar :  0

Se elimina impar
  estados: ini par fin
  ini -> par :  ε
  par -> par :  0|10*1
  par -> fin :  ε

Se elimina par
  estados: ini fin
  ini -> fin :  (0|10*1)*

Expresión: (0|10*1)*

Error común. Al eliminar un estado, olvidar su ciclo o alguna de las parejas. Sin el ciclo, la flecha reparada sería 0∪11\mathtt{0} \cup \mathtt{11}, y se perderían todas las cadenas que dan vueltas en impar\mathit{impar}, como 101\mathtt{101}. El otro olvido es más frecuente cuando el estado tiene varias entradas y varias salidas: con 2 que entran y 3 que salen son 6 parejas, y cada una que falte quita cadenas del lenguaje. Por eso conviene hacer las dos listas antes de calcular nada, y contar.

Un ejemplo completo: los múltiplos de 3

El DFA de tres estados de la semana 1 que reconoce los múltiplos de 3 en binario está en machines/multiple_of_3.dfa. El estado rir_i dice que el valor de lo leído deja resto ii al dividir entre 3.

δ\delta 0\mathtt{0} 1\mathtt{1}
r0r_0 (inicial, de aceptación) r0r_0 r1r_1
r1r_1 r2r_2 r0r_0
r2r_2 r1r_1 r2r_2

¿Qué expresión regular describe los múltiplos de 3? No es nada evidente, y con el método sale sin pensar. Eliminaremos en el orden r2r_2, r1r_1, r0r_0.

El GNFA inicial. Cinco estados y ocho flechas.

$ build/eliminate machines/multiple_of_3.dfa r2 r1 r0
Autómata generalizado de machines/multiple_of_3.dfa
  estados: ini r0 r1 r2 fin
  ini -> r0 :  ε
  r0 -> r0 :  0
  r0 -> r1 :  1
  r0 -> fin :  ε
  r1 -> r0 :  1
  r1 -> r2 :  0
  r2 -> r1 :  0
  r2 -> r2 :  1

Se elimina r2r_2. Entra r1r_1, con 0\mathtt{0}. Sale r1r_1, con 0\mathtt{0}. El ciclo es 1\mathtt{1}. Hay una sola pareja, (r1,r1)(r_1, r_1), y r1r_1 no tenía ciclo:

R11′=∅∪0 (1)∗ 0=01∗0R_{11}' = \emptyset \cup \mathtt{0}\,(\mathtt{1})^*\,\mathtt{0} = \mathtt{0}\mathtt{1}^*\mathtt{0}
Se elimina r2
  estados: ini r0 r1 fin
  ini -> r0 :  ε
  r0 -> r0 :  0
  r0 -> r1 :  1
  r0 -> fin :  ε
  r1 -> r0 :  1
  r1 -> r1 :  01*0

La flecha nueva resume toda excursión de r1r_1 a r2r_2 y de vuelta. Las otras cinco flechas no cambiaron, porque sus parejas no tenían desvío por r2r_2.

Se elimina r1r_1. Entra r0r_0, con 1\mathtt{1}. Sale r0r_0, con 1\mathtt{1}. El ciclo es 01∗0\mathtt{0}\mathtt{1}^*\mathtt{0}. Otra vez una sola pareja, (r0,r0)(r_0, r_0), que ya tenía el ciclo 0\mathtt{0}:

R00′=0∪1 (01∗0)∗ 1R_{00}' = \mathtt{0} \cup \mathtt{1}\,(\mathtt{0}\mathtt{1}^*\mathtt{0})^*\,\mathtt{1}
Se elimina r1
  estados: ini r0 fin
  ini -> r0 :  ε
  r0 -> r0 :  0|1(01*0)*1
  r0 -> fin :  ε

Se elimina r0r_0. Entra qiniq_{\text{ini}} con ε\varepsilon, sale qfinq_{\text{fin}} con ε\varepsilon:

Rini,fin′=∅∪ε (0∪1(01∗0)∗1)∗ ε=(0∪1(01∗0)∗1)∗R_{\text{ini},\text{fin}}' = \emptyset \cup \varepsilon\,(\mathtt{0} \cup \mathtt{1}(\mathtt{0}\mathtt{1}^*\mathtt{0})^*\mathtt{1})^*\,\varepsilon = (\mathtt{0} \cup \mathtt{1}(\mathtt{0}\mathtt{1}^*\mathtt{0})^*\mathtt{1})^*
Se elimina r0
  estados: ini fin
  ini -> fin :  (0|1(01*0)*1)*

Expresión: (0|1(01*0)*1)*
Animación de la eliminación de estados en el autómata de los múltiplos de 3, en cuatro pasos. Paso 1, el GNFA inicial: a la izquierda q_ini arriba, con la flecha de inicio, y q_fin abajo, con doble círculo; a la derecha, en fila, r₀, r₁ y r₂. Hay una flecha ε de q_ini a r₀ y otra de r₀ a q_fin; r₀ tiene un bucle con 0; entre r₀ y r₁ hay una flecha con 1 en cada sentido; entre r₁ y r₂, una flecha con 0 en cada sentido; r₂ tiene un bucle con 1. Paso 2, se elimina r₂: se resaltan r₂ y sus tres flechas, desaparecen, y r₁ gana un bucle con 01*0. Paso 3, se elimina r₁: se resaltan r₁, su bucle y las dos flechas con 1, desaparecen, y el bucle de r₀ pasa de 0 a 0 ∪ 1(01*0)*1. Paso 4, se elimina r₀: desaparece con sus flechas ε, y queda una sola flecha de q_ini a q_fin con la expresión (0 ∪ 1(01*0)*1)*. Al pie de cada paso se lee quién entra, quién sale y cuál es el ciclo del estado que se eliminaAnimación de la eliminación de estados en el autómata de los múltiplos de 3, en cuatro pasos. Paso 1, el GNFA inicial: a la izquierda q_ini arriba, con la flecha de inicio, y q_fin abajo, con doble círculo; a la derecha, en fila, r₀, r₁ y r₂. Hay una flecha ε de q_ini a r₀ y otra de r₀ a q_fin; r₀ tiene un bucle con 0; entre r₀ y r₁ hay una flecha con 1 en cada sentido; entre r₁ y r₂, una flecha con 0 en cada sentido; r₂ tiene un bucle con 1. Paso 2, se elimina r₂: se resaltan r₂ y sus tres flechas, desaparecen, y r₁ gana un bucle con 01*0. Paso 3, se elimina r₁: se resaltan r₁, su bucle y las dos flechas con 1, desaparecen, y el bucle de r₀ pasa de 0 a 0 ∪ 1(01*0)*1. Paso 4, se elimina r₀: desaparece con sus flechas ε, y queda una sola flecha de q_ini a q_fin con la expresión (0 ∪ 1(01*0)*1)*. Al pie de cada paso se lee quién entra, quién sale y cuál es el ciclo del estado que se elimina
Cada eliminación quita un estado y deja su rastro en una flecha. Cuando solo quedan el estado inicial y el de aceptación, la expresión de la única flecha es la respuesta.

La respuesta. Los múltiplos de 3 en binario son

(0∪1(01∗0)∗1)∗(\mathtt{0} \cup \mathtt{1}(\mathtt{0}\mathtt{1}^*\mathtt{0})^*\mathtt{1})^*

La expresión se puede leer, ahora que la tenemos. Un múltiplo de 3 es una secuencia de vueltas desde el resto 0 hasta el resto 0. La vuelta corta es un 0\mathtt{0}, que duplica el valor y conserva el resto. La larga sale con un 1\mathtt{1} al resto 1, hace cualquier número de excursiones 01∗0\mathtt{0}\mathtt{1}^*\mathtt{0} al resto 2 y de vuelta, y regresa con un 1\mathtt{1}. Por ejemplo, 1001\mathtt{1001}, que es 9, es una vuelta larga con una excursión 00\mathtt{00}. Y 110\mathtt{110}, que es 6, son dos vueltas: 11\mathtt{11} y 0\mathtt{0}.

Las pruebas de la semana cierran el círculo con esta expresión: la convierten en un NFA con la construcción de Thompson y comprueban que ese NFA y el DFA original responden lo mismo con todas las cadenas cortas.

Por qué funciona la eliminación

Afirmación. Sea GG un GNFA con al menos tres estados, y G′G' el que resulta de eliminar el estado qkq_k con la regla. Entonces GG y G′G' aceptan las mismas cadenas.

Demostración. En las dos direcciones. Escribimos RijR_{ij} para las expresiones de GG y Rij′R_{ij}' para las de G′G'.

Lo que acepta GG lo acepta G′G'. Supongamos que GG acepta ww con los estados p0,p1,…,pmp_0, p_1, \ldots, p_m y los trozos w1,…,wmw_1, \ldots, w_m. Si qkq_k no aparece entre los estados, la misma secuencia sirve en G′G': cada Rij′R_{ij}' es una unión que contiene a RijR_{ij}, así que cada trozo sigue estando en el lenguaje de su flecha.

Si qkq_k aparece, miramos cada racha de apariciones seguidas. Una racha no está al principio ni al final, porque qkq_k no es qiniq_{\text{ini}} ni qfinq_{\text{fin}}: tiene un estado antes, qiq_i, y uno después, qjq_j, y los dos son distintos de qkq_k. Los trozos que se leen desde qiq_i hasta qjq_j son: uno de L(Rik)L(R_{ik}), para entrar; uno de L(Rkk)L(R_{kk}) por cada paso de qkq_k a qkq_k dentro de la racha, que pueden ser cero; y uno de L(Rkj)L(R_{kj}), para salir. Su concatenación está en L(Rik(Rkk)∗Rkj)L(R_{ik}(R_{kk})^*R_{kj}), y por lo tanto en L(Rij′)L(R_{ij}'). Reemplazamos toda la racha por un solo paso de qiq_i a qjq_j que lee esa concatenación. Los pasos que no tocan a qkq_k sirven tal cual, como en el caso anterior. Hecho esto con cada racha, queda una secuencia sin qkq_k que cumple la definición en G′G' y lee la misma ww.

Lo que acepta G′G' lo acepta GG. Supongamos que G′G' acepta ww con ciertos estados y trozos. Miramos cada paso, de qiq_i a qjq_j con el trozo xx. Como x∈L(Rij′)=L(Rij)∪L(Rik(Rkk)∗Rkj)x \in L(R_{ij}') = L(R_{ij}) \cup L(R_{ik}(R_{kk})^*R_{kj}), hay dos casos. Si x∈L(Rij)x \in L(R_{ij}), el mismo paso existe en GG. Si no, x=yz1⋯ztux = y z_1 \cdots z_t u con y∈L(Rik)y \in L(R_{ik}), cada zz en L(Rkk)L(R_{kk}), t≥0t \geq 0 y u∈L(Rkj)u \in L(R_{kj}): en GG reemplazamos el paso por el desvío qi,qk,…,qk,qjq_i, q_k, \ldots, q_k, q_j, que lee esos mismos trozos. La secuencia que resulta cumple la definición en GG y lee la misma ww. ∎

Con la afirmación, el algoritmo completo queda demostrado.

Teorema. Para todo DFA MM hay una expresión regular RR con L(R)=L(M)L(R) = L(M).

Demostración. Por construcción. Se normaliza MM para obtener un GNFA con ∣Q∣+2|Q| + 2 estados, que acepta lo mismo que MM. Se eliminan los estados de MM uno por uno, en cualquier orden: cada eliminación conserva las cadenas aceptadas. Después de ∣Q∣|Q| eliminaciones quedan qiniq_{\text{ini}} y qfinq_{\text{fin}}, con una sola flecha entre ellos, que lleva una expresión RR. Un GNFA de esa forma acepta ww si y solo si w∈L(R)w \in L(R): la única secuencia de estados posible es qini,qfinq_{\text{ini}}, q_{\text{fin}}, con ww entera como único trozo. Entonces L(R)=L(M)L(R) = L(M). ∎

Dos observaciones sobre la demostración.

  • Vale para cualquier orden. La afirmación no pide nada de qkq_k, salvo que no sea uno de los dos estados especiales. El orden no cambia el lenguaje. Sí cambia la expresión, como veremos enseguida.
  • Vale también para un NFA. La normalización funciona igual con un NFA: sus flechas ya llevan símbolos o ε\varepsilon. Empezamos por un DFA porque es el caso que ya tienen en machines/.

El orden de eliminación

La paridad, eliminando primero par\mathit{par} y después impar\mathit{impar}:

$ build/eliminate machines/even_ones.dfa par impar
Autómata generalizado de machines/even_ones.dfa
  estados: ini par impar fin
  ini -> par :  ε
  par -> par :  0
  par -> impar :  1
  par -> fin :  ε
  impar -> par :  1
  impar -> impar :  0

Se elimina par
  estados: ini impar fin
  ini -> impar :  0*1
  ini -> fin :  0*
  impar -> impar :  0|10*1
  impar -> fin :  10*

Se elimina impar
  estados: ini fin
  ini -> fin :  0*|0*1(0|10*1)*10*

Expresión: 0*|0*1(0|10*1)*10*

Esta vez par\mathit{par} tenía dos que entran, qiniq_{\text{ini}} e impar\mathit{impar}, y dos que salen, impar\mathit{impar} y qfinq_{\text{fin}}: cuatro parejas, y las cuatro flechas nuevas están en la salida. El resultado es

0∗∪0∗1(0∪10∗1)∗10∗\mathtt{0}^* \cup \mathtt{0}^*\mathtt{1}(\mathtt{0} \cup \mathtt{1}\mathtt{0}^*\mathtt{1})^*\mathtt{1}\mathtt{0}^*

que tiene 22 nodos, contra los 9 de (0∪10∗1)∗(\mathtt{0} \cup \mathtt{1}\mathtt{0}^*\mathtt{1})^*. Las dos describen las cadenas con un número par de unos. La segunda las ve desde impar\mathit{impar}: o la cadena no tiene unos, o tiene ceros, un 1\mathtt{1} que lleva a impar\mathit{impar}, vueltas desde impar\mathit{impar}, y un 1\mathtt{1} final de regreso con sus ceros.

Con tres estados hay seis órdenes. El programa orders los prueba todos:

$ build/orders machines/multiple_of_3.dfa
r0 r1 r2  (65 nodos)
    0*|0*1(10*1)*10*|0*1(10*1)*0(1|0(10*1)*0)*0(10*1)*10*
r0 r2 r1  (27 nodos)
    0*|0*1(10*1|01*0)*10*
r1 r0 r2  (50 nodos)
    (0|11)*|(0|11)*10(1|00|01(0|11)*10)*01(0|11)*
r1 r2 r0  (21 nodos)
    (0|11|10(1|00)*01)*
r2 r0 r1  (27 nodos)
    0*|0*1(01*0|10*1)*10*
r2 r1 r0  (14 nodos)
    (0|1(01*0)*1)*

Seis expresiones distintas para el mismo lenguaje, de 14 a 65 nodos. La mejor es la del ejemplo, y la peor es la que sale con el orden del archivo. En las dos más cortas, el estado r0r_0 se elimina al final. No es casualidad: r0r_0 es el inicial y el de aceptación, así que es el más conectado del GNFA. Eliminarlo temprano crea muchas parejas, y sus expresiones se copian después en todas las flechas que se reparan.

Idea clave. El orden de eliminación cambia la expresión que sale y no el lenguaje. Una regla práctica: eliminar primero los estados con pocas flechas, pocos que entran y pocos que salen, y dejar para el final los más conectados.

Las expresiones crecen rápido

En cada eliminación, la expresión nueva de una pareja contiene hasta cuatro expresiones anteriores: RijR_{ij}, RikR_{ik}, RkkR_{kk} y RkjR_{kj}. Si todas tienen tamaño a lo sumo ss, la nueva tiene a lo sumo 4s+44s + 4 nodos: las cuatro, más una unión, dos concatenaciones y una estrella. El tamaño puede cuadruplicarse en cada paso, y después de eliminar nn estados puede ser del orden de 4n4^n.

El programa growth lo mide con una familia de autómatas: para cada kk, el DFA de kk estados de los múltiplos de kk en binario, que se construye igual que el de los múltiplos de 3. Elimina los estados en dos órdenes: con r0r_0 primero, y con r0r_0 al final.

$ build/growth
 k   estados   nodos (r0 primero)   nodos (r0 al final)
 2         2                   22                     9
 3         3                   65                    14
 4         4                  110                    27
 5         5                  314                    52
 6         6                  384                    67
 7         7                 1341                   209
 8         8                 1636                   267

Con 8 estados, el DFA cabe en una tabla de 16 casillas y la expresión tiene cientos de nodos, o más de mil con el orden malo. Un buen orden ayuda mucho y no cambia el fondo: se ha demostrado que para algunos autómatas toda expresión equivalente es exponencialmente más grande que el autómata. Pasar de la máquina a la descripción es caro, y no por culpa del método.

La eliminación tampoco promete la expresión más corta. Para el autómata de las cadenas que terminan en 01\mathtt{01}, de la semana 1, uno de los órdenes da esto (los puntos suspensivos marcan la parte de la salida que aquí se omite):

$ build/eliminate machines/ends_01.dfa q2 q0 q1
...
Expresión: 1*0(0|10|111*0)*1

Es correcta, y cualquiera habría escrito (0∪1)∗01(\mathtt{0} \cup \mathtt{1})^*\mathtt{01}.

$ build/regex_diff '1*0(0|10|111*0)*1' '(0|1)*01' 10
R1 = 1*0(0|10|111*0)*1
R2 = (0|1)*01
2047 cadenas de longitud a lo sumo 10
solo en R1: 0
solo en R2: 0
sin diferencias hasta esa longitud

A cambio, el método resuelve lo que a mano cuesta. El lenguaje de las cadenas sin 11\mathtt{11}, que en la sesión A pidió una idea y dos intentos, sale de su DFA de tres estados, el de machines/no_11.dfa, sin pensar nada. Ese autómata tiene un estado trampa, q2q_2, al que se llega cuando aparece 11\mathtt{11}:

$ build/eliminate machines/no_11.dfa q2 q1 q0
...
Se elimina q2
  estados: ini q0 q1 fin
  ini -> q0 :  ε
  q0 -> q0 :  0
  q0 -> q1 :  1
  q0 -> fin :  ε
  q1 -> q0 :  0
  q1 -> fin :  ε

Se elimina q1
  estados: ini q0 fin
  ini -> q0 :  ε
  q0 -> q0 :  0|10
  q0 -> fin :  ε|1

Se elimina q0
  estados: ini fin
  ini -> fin :  (0|10)*(ε|1)

Expresión: (0|10)*(ε|1)

Es exactamente la expresión de la sesión A. Y miren lo que pasó con la trampa: a q2q_2 entraba una flecha y no salía ninguna, así que no había ninguna pareja que reparar, y el estado desapareció sin dejar rastro. Un estado desde el que no se puede llegar a la aceptación no aporta nada a la expresión.

El teorema de Kleene

Teorema (Kleene). Un lenguaje es regular si y solo si alguna expresión regular lo describe.

Demostración. Las dos direcciones ya están hechas.

Si una expresión RR describe el lenguaje, la construcción de Thompson da un NFA que reconoce L(R)L(R), y la construcción de subconjuntos de la semana pasada lo convierte en un DFA. Entonces el lenguaje es regular.

Si el lenguaje es regular, algún DFA lo reconoce, y la eliminación de estados da una expresión que lo describe. ∎

El teorema lleva el nombre de Stephen Kleene, que lo demostró en 1956, y que es también el Kleene de la estrella. Con él se cierra un triángulo: tres maneras de dar un lenguaje, y una conversión de cada una a la siguiente.

Un triángulo con un modelo en cada vértice: arriba, expresión regular, que describe el lenguaje; abajo a la izquierda, NFA, que lo reconoce adivinando; abajo a la derecha, DFA, que lo reconoce con una tabla. Una flecha baja de la expresión regular al NFA: Thompson, semana 3, lineal, a lo sumo 2|R| estados. Una flecha va del NFA al DFA: subconjuntos, semana 2, hasta 2ⁿ estados. Una flecha sube del DFA a la expresión regular: eliminación de estados, semana 3, hasta del orden de 4ⁿ nodos. Una flecha punteada vuelve del DFA al NFA: ninguna construcción, porque todo DFA es un NFA. En el centro: los mismos lenguajes, los regularesUn triángulo con un modelo en cada vértice: arriba, expresión regular, que describe el lenguaje; abajo a la izquierda, NFA, que lo reconoce adivinando; abajo a la derecha, DFA, que lo reconoce con una tabla. Una flecha baja de la expresión regular al NFA: Thompson, semana 3, lineal, a lo sumo 2|R| estados. Una flecha va del NFA al DFA: subconjuntos, semana 2, hasta 2ⁿ estados. Una flecha sube del DFA a la expresión regular: eliminación de estados, semana 3, hasta del orden de 4ⁿ nodos. Una flecha punteada vuelve del DFA al NFA: ninguna construcción, porque todo DFA es un NFA. En el centro: los mismos lenguajes, los regulares
El triángulo de Kleene: de cada modelo se pasa al siguiente con una construcción, y por eso los tres describen la misma clase de lenguajes.
Conversión Construcción Tamaño del resultado
Expresión →\to NFA Thompson, esta semana Lineal: a lo sumo 2 ∣R∣2\,\lvert R\rvert estados
NFA →\to DFA Subconjuntos, semana 2 Hasta 2n2^n estados
DFA →\to expresión Eliminación de estados, esta semana Hasta el orden de 4n4^n nodos
DFA →\to NFA Ninguna: todo DFA es un NFA El mismo

Dos de los tres lados pueden ser exponenciales. Los tres modelos tienen el mismo poder, y no la misma economía: un mismo lenguaje puede ser corto de describir y largo de reconocer con un DFA, o al revés.

Lo que el teorema permite, en la práctica:

  • Elegir el modelo según el problema. Para demostrar que un lenguaje es regular basta dar un DFA, un NFA o una expresión, lo que salga más fácil. “Termina en 01\mathtt{01}” es más fácil como expresión. “Múltiplo de 3” es más fácil como DFA.
  • Usar las propiedades de cierre con expresiones. Las expresiones no tienen complemento ni intersección, pero los lenguajes que describen son cerrados bajo los dos. Para obtener la expresión del complemento de L(R)L(R): de RR a un NFA, de ahí a un DFA, se intercambian los estados de aceptación, y se eliminan estados. La expresión existe siempre, aunque pueda ser enorme.
  • Decidir preguntas sobre expresiones. ¿Describen dos expresiones el mismo lenguaje? Se convierten las dos en DFA y se comparan los autómatas, con la construcción del producto de la semana 1. Sobre las fórmulas, la pregunta no tiene por dónde tomarse. Sobre los autómatas es un recorrido de un grafo.

Idea clave. Regular es una sola clase de lenguajes con tres definiciones equivalentes: lo que reconoce un DFA, lo que reconoce un NFA y lo que describe una expresión regular. Que tres definiciones tan distintas coincidan es la señal de que la clase es natural, y no un accidente de cómo definimos la máquina.

Cómo busca un motor real

El teorema dice que una expresión se puede convertir en una máquina. Un programa como grep tiene que decidir además cómo ejecutarla, y ahí hay dos familias de motores que se comportan de manera muy distinta.

Simular el NFA

La primera es la de este capítulo: construir el NFA de Thompson y seguirlo con el conjunto de estados activos, como hace run_nfa.

algoritmo simular(N, w)
    activos ← clausura_ε({q0})
    para cada símbolo a de w, en orden
        siguientes ← ∅
        para cada estado q de activos
            agregar a siguientes los estados de δ(q, a)
        fin para
        activos ← clausura_ε(siguientes)
    fin para
    devolver si activos contiene un estado de F
fin algoritmo

¿Cuánto cuesta? Sea n=∣w∣n = |w| y sea mm el número de estados del NFA. El conjunto de activos nunca tiene más de mm estados. En cada vuelta del ciclo, cada estado activo se mira una vez, y la clausura ε\varepsilon es una búsqueda en un grafo, que visita cada estado y cada flecha a lo sumo una vez. En el NFA de Thompson salen a lo sumo dos flechas de cada estado, así que una vuelta cuesta O(m)O(m). Son nn vueltas:

O(n⋅m),y como m≤2 ∣R∣, es O(∣w∣⋅∣R∣).O(n \cdot m), \qquad \text{y como } m \leq 2\,|R|, \text{ es } O(|w| \cdot |R|).

El costo es el producto de la longitud del texto por el tamaño de la expresión, siempre: no depende de qué expresión sea ni de qué cadena. La memoria es O(m)O(m), y no crece con la cadena.

Probar los caminos uno por uno

La segunda familia hace lo que haría una persona con paciencia: backtracking. Recorre la expresión y, cada vez que hay una elección (cuál de las dos ramas de una unión, dar otra vuelta en una estrella o salir), prueba una. Si más adelante la búsqueda fracasa, vuelve a la última elección y prueba la otra.

Es fácil de programar: la función match de backtrack.h son unas veinticinco líneas, con un caso por cada tipo de nodo. Y casi siempre es rápida, porque casi siempre la primera elección es la buena.

$ build/backtrack '(a|a)*b' aaab aaa
aaab: acepta, 15 llamadas
aaa: rechaza, 76 llamadas

La expresión (a∪a)∗b(\mathtt{a} \cup \mathtt{a})^*\mathtt{b} es rara a propósito: las dos ramas de la unión son iguales. Describe las cadenas anb\mathtt{a}^n\mathtt{b}. Con aaab\mathtt{aaab}, la búsqueda acierta a la primera. Con aaa\mathtt{aaa} tiene que rechazar, y para rechazar debe convencerse de que ninguna combinación de elecciones funciona. Cada a\mathtt{a} se puede leer con la rama izquierda o con la derecha. Para tres letras hay 23=82^3 = 8 combinaciones, y todas fracasan al final por lo mismo: falta la b\mathtt{b}. La búsqueda las recorre todas.

Se puede contar con exactitud. Sea S(n)S(n) el número de llamadas que hace match para la estrella cuando quedan nn letras a\mathtt{a}. La estrella llama a la unión, que llama a sus dos ramas, y cada rama lee una a\mathtt{a} y vuelve a llamar a la estrella con n−1n - 1 letras. Cuando las dos fracasan, sale de la estrella y prueba la b\mathtt{b}. Son 5 llamadas propias y dos llamadas recursivas:

S(0)=5,S(n)=5+2 S(n−1),de donde S(n)=10⋅2n−5.S(0) = 5, \qquad S(n) = 5 + 2\,S(n - 1), \qquad \text{de donde } S(n) = 10 \cdot 2^n - 5.

Con la llamada inicial, la de la concatenación, el total es 10⋅2n−410 \cdot 2^n - 4. Para n=3n = 3 da 76, lo que imprimió el programa. Cada letra más duplica el trabajo.

make bench compila las dos búsquedas con -O2, sin sanitizers, y las corre con cadenas an\mathtt{a}^n cada vez más largas. Esta es una ejecución en el contenedor del curso, en una laptop:

$ make bench
build/matchers_bench
expresión: (a|a)*b    cadena: a^n    NFA de Thompson: 10 estados

      n   backtracking: llamadas   backtracking: tiempo   NFA: tiempo
      5                      316               0.0000 s      0.0000 s
     10                    10236               0.0000 s      0.0000 s
     15                   327676               0.0013 s      0.0000 s
     20                 10485756               0.0434 s      0.0000 s
     25                335544316               1.3842 s      0.0000 s
   1000                        -                      -      0.0009 s
 100000                        -                      -      0.0871 s

Los tiempos cambian de una máquina a otra y de una ejecución a la siguiente. Las llamadas no: son las de la fórmula. Con n=25n = 25, el backtracking ya tarda más de un segundo. Con n=35n = 35 serían 2102^{10} veces más, más de veinte minutos, y con n=100n = 100 no terminaría nunca. La simulación del NFA lee una cadena de 100 000 letras en menos de una décima de segundo, y eso con la versión de nfa.h, que guarda los estados como cadenas en un std::set y no está hecha para correr rápido.

¿Por qué una es exponencial y la otra no, si las dos exploran el mismo autómata? Porque el backtracking recorre caminos, y la simulación recorre estados. Después de leer kk letras hay 2k2^k caminos distintos, y todos están en el mismo lugar de la expresión. El backtracking no lo sabe y los visita uno por uno. La simulación guarda un conjunto: los 2k2^k caminos que llegan al mismo estado ocupan un solo lugar en él. Es la misma observación de la semana 1, que sostiene todo lo regular: lo único que importa de lo leído es el estado al que se llegó.

Idea clave. Simular el NFA con el conjunto de estados activos cuesta O(∣w∣⋅∣R∣)O(|w| \cdot |R|) para toda expresión y toda cadena. El backtracking es correcto, y con algunas expresiones tarda un tiempo exponencial en ∣w∣|w|, porque recorre uno por uno caminos que terminan en el mismo estado.

En la práctica. Las dos familias existen. grep, y las bibliotecas de expresiones regulares de Go y de Rust, trabajan con autómatas y garantizan un tiempo lineal en el texto. Las de Perl, Python, Java y JavaScript usan backtracking. En el contenedor del curso, re.fullmatch('(a|a)*b', 'a' * n) de Python 3.14 tardó 0,05 segundos con n=20n = 20 y 1,47 segundos con n=25n = 25. grep -xE '(a|a)*b' respondió en 0,001 segundos con una línea de 100 000 letras. Cuando el patrón o el texto vienen de un usuario, un patrón así se convierte en un ataque: basta enviar una cadena de unas decenas de caracteres para ocupar un procesador durante horas.

Un motor basado en autómatas suele ir un paso más allá: guarda cada conjunto de estados activos la primera vez que lo calcula, y también a qué conjunto lleva con cada símbolo. Eso es la construcción de subconjuntos de la semana pasada, hecha sobre la marcha: solo se construyen los estados del DFA que el texto realmente visita.

Lo que no es regular: las referencias hacia atrás

Si simular el NFA es mejor, ¿por qué tantos lenguajes usan backtracking? Una razón es histórica. La otra es que sus patrones tienen operadores que la simulación no puede manejar. El principal es la referencia hacia atrás: \1 significa “aquí va otra vez el mismo texto que coincidió con el primer paréntesis”.

((a|b)*)\1

El primer paréntesis es (a∪b)∗(\mathtt{a} \cup \mathtt{b})^* entero. Con grep -xE, este patrón coincide con abab\mathtt{abab} y con bbabba\mathtt{bbabba}, y no con abba\mathtt{abba}: describe las cadenas de la forma wwww, una cadena cualquiera seguida de una copia exacta de sí misma. No es una abreviatura, porque no se puede reescribir con unión, concatenación y estrella: el lenguaje { ww:w∈{a,b}∗ }\{\, ww : w \in \{\mathtt{a}, \mathtt{b}\}^* \,\} no es regular. Para reconocerlo hay que recordar la primera mitad entera, y un autómata finito no puede recordar una cadena de longitud arbitraria. Por ahora es solo un enunciado. La demostración llega la semana próxima, con las herramientas para probar que un lenguaje no es regular.

Así que el nombre engaña: las regex con referencias hacia atrás describen más que los lenguajes regulares, y pagan por ello. Ningún autómata finito las ejecuta, y de ahí el backtracking.

El código de la semana

code/week-03/
├── regex.h               el árbol de una expresión, el parser y la escritura con los paréntesis justos
├── nfa.h                 struct Nfa, lectura del formato .nfa, clausura ε y estados activos
├── thompson.h            construcción de Thompson: de expresión a NFA
├── dfa.h                 struct Dfa, el de la semana 1
├── gnfa.h                autómata generalizado y eliminación de estados: de DFA a expresión
├── backtrack.h           el buscador con backtracking, que cuenta sus llamadas
├── words.h               todas las cadenas hasta una longitud
├── regex_tree.cpp        muestra el árbol de una expresión
├── regex_lang.cpp        lista las cadenas más cortas del lenguaje de una expresión
├── regex_diff.cpp        compara dos expresiones con todas las cadenas cortas
├── thompson.cpp          escribe el NFA de una expresión en formato .nfa
├── run_nfa.cpp           sigue un NFA con una cadena, mostrando los estados activos
├── eliminate.cpp         elimina los estados de un DFA en el orden que se le pida
├── orders.cpp            prueba todos los órdenes de eliminación
├── growth.cpp            mide cuánto crece la expresión con el número de estados
├── backtrack.cpp         busca con backtracking y cuenta las llamadas
├── matchers_bench.cpp    backtracking frente a simulación del NFA (make bench)
├── machines/             los autómatas del capítulo, en formato .dfa y .nfa
├── errors/               expresiones mal formadas
├── test_regex.cpp        el parser: precedencia, ε y ∅, errores
├── test_thompson.cpp     cada expresión contra un predicado; la forma del NFA; las identidades
├── test_elimination.cpp  DFA → expresión → NFA, con todos los órdenes de eliminación
├── test_backtrack.cpp    el backtracking contra el NFA, y la fórmula de las llamadas
└── lab/mini_grep/        el laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan. Tardan unos segundos: la simulación de nfa.h trabaja con nombres de estados, y bajo los sanitizers es lenta.

$ make test
test_regex: ok (9 expresiones mal formadas rechazadas)
test_thompson: ok (15 expresiones contra su predicado)
test_elimination: ok (4 autómatas, 20 órdenes de eliminación, 511 cadenas cada uno)
test_backtrack: ok (14 expresiones, 511 cadenas cada una)
Todas las pruebas pasaron.

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

  • test_regex revisa la precedencia con la forma del árbol, que % y @ se lean como ε\varepsilon y ∅\emptyset, que lo que el programa escribe se pueda volver a leer, y que cada expresión de errors/malformed.txt se rechace.
  • test_thompson convierte en NFA cada expresión de la sesión A y la compara con una función de C++ que decide el mismo lenguaje mirando la cadena completa, sobre las 1023 cadenas binarias de longitud a lo sumo 9. Comprueba además la forma del autómata (un estado de aceptación, a lo sumo dos flechas por estado, exactamente 2⋅(hojas+uniones+estrellas)2 \cdot (\text{hojas} + \text{uniones} + \text{estrellas}) estados), las identidades de la tabla y la ejecución de 011\mathtt{011} copiada arriba.
  • test_elimination es la prueba del teorema de Kleene con ejemplos. Para cada DFA de machines/ y cada orden de eliminación, toma la expresión que sale, la escribe, la vuelve a leer, la convierte en un NFA con Thompson y compara ese NFA con el DFA original sobre las 511 cadenas de longitud a lo sumo 8. También comprueba las expresiones intermedias de los ejemplos y los tamaños de la tabla de growth hasta k=5k = 5.
  • test_backtrack comprueba que el backtracking responde lo mismo que el NFA, que termina con estrellas anidadas como (0∗)∗(\mathtt{0}^*)^*, y que con (a∪a)∗b(\mathtt{a} \cup \mathtt{a})^*\mathtt{b} hace exactamente 10⋅2n−410 \cdot 2^n - 4 llamadas para nn de 0 a 14.

Los archivos de machines/ son:

Archivo Lenguaje Estados
even_ones.dfa Cantidad par de unos, de la semana 1 2
multiple_of_3.dfa Múltiplos de 3 en binario, de la semana 1 3
ends_01.dfa Termina en 01\mathtt{01}, de la semana 1 3
no_11.dfa No contiene 11\mathtt{11}, con estado trampa 3
ends_in_1.nfa El NFA de Thompson de (0∪1)∗1(\mathtt{0} \cup \mathtt{1})^*\mathtt{1} 10
ab_or_a_star.nfa El NFA de Thompson de (ab∪a)∗(\mathtt{ab} \cup \mathtt{a})^* 10

Para experimentar: escriban un DFA propio en machines/, pásenlo por orders, tomen la expresión más corta y compárenla con regex_diff contra la que ustedes habrían escrito. O al revés: escriban una expresión, conviértanla con thompson, guarden la salida en un archivo .nfa y síganla con run_nfa.

Dos decisiones del código que conviene conocer.

  • En nfa.h, δ\delta es un std::map de (estado, símbolo) a un std::set de nombres, y una transición ε\varepsilon se guarda con el carácter '\0' en el lugar del símbolo. Se eligió así para que el código se lea como la definición, δ:Q×(Σ∪{ε})→P(Q)\delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q), y no por velocidad. Para el laboratorio hace falta otra representación.
  • gnfa.h aplica al construir cada expresión las identidades de ∅\emptyset y de ε\varepsilon, y ninguna otra. No reconoce, por ejemplo, que R∪R=RR \cup R = R. Por eso las expresiones que imprime son correctas y no siempre las más cortas.

El laboratorio

En lab/mini_grep está el enunciado, un esqueleto y los casos. El problema es un grep pequeño: la entrada es una expresión regular con |, concatenación, * y paréntesis, seguida de una lista de líneas, y la salida dice por cada línea si la expresión la describe completa.

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

Son los tres pasos de la sesión A, uno detrás de otro: el árbol de la expresión, respetando la precedencia; el NFA de Thompson; y la simulación con el conjunto de estados activos. Entre los casos están la expresión (a∪a)∗b(\mathtt{a} \cup \mathtt{a})^*\mathtt{b} contra líneas largas de letras a\mathtt{a}, y estrellas anidadas, que forman ciclos de transiciones ε\varepsilon. Una solución con backtracking pasa los casos pequeños y se queda sin tiempo en esos.

Como en la semana 1, solution.cpp se escribe sin incluir los encabezados de esta carpeta: el juez compila ese único archivo. Pueden leer regex.h y thompson.h cuanto quieran, pero no les conviene copiarlos tal cual, porque con nombres de estados en un std::set la simulación es demasiado lenta. Numeren los estados y usen arreglos.

Resumen

  • Una expresión regular se define por casos: un símbolo, ε\varepsilon, ∅\emptyset, y la unión, la concatenación y la estrella de expresiones más pequeñas. L(R)L(R) es el lenguaje que describe.
  • Precedencia: estrella, concatenación, unión. 01∗\mathtt{01}^* es 0(1∗)\mathtt{0}(\mathtt{1}^*). Una expresión es un árbol, y su tamaño ∣R∣|R| es el número de nodos.
  • En la teoría la unión se escribe ∪\cup, y en el código y en las herramientas, |.
  • Para escribir una expresión se piensa en cómo se parte una cadena en trozos. Se prueba con cadenas de los dos lados: una expresión puede describir de menos o de más.
  • Identidades: R∪∅=RR \cup \emptyset = R, Rε=RR\varepsilon = R, R∅=∅R\emptyset = \emptyset y ∅∗=ε\emptyset^* = \varepsilon. Son falsas R∪ε=RR \cup \varepsilon = R y R∅=RR\emptyset = R.
  • La construcción de Thompson convierte una expresión en un NFA: una pieza por nodo del árbol, con una entrada y una salida, unidas con transiciones ε\varepsilon. Se demuestra por inducción sobre la estructura de la expresión. El NFA tiene a lo sumo 2 ∣R∣2\,|R| estados, y de cada uno salen a lo sumo dos flechas.
  • Las abreviaturas de las herramientas (+, ?, [a-z], {n,m}) se reescriben con las tres operaciones y no agregan poder. grep busca el patrón dentro de la línea: Σ∗R Σ∗\Sigma^*R\,\Sigma^*.
  • Un GNFA lleva expresiones en las flechas, tiene un estado inicial sin flechas que entren y un único estado de aceptación sin flechas que salgan. Un DFA se normaliza con dos estados nuevos y transiciones ε\varepsilon.
  • Eliminar el estado qkq_k: cada pareja (qi,qj)(q_i, q_j) pasa a llevar Rij∪Rik(Rkk)∗RkjR_{ij} \cup R_{ik}(R_{kk})^*R_{kj}. No hay que olvidar el ciclo ni ninguna pareja. Cuando quedan dos estados, la expresión de la única flecha es la respuesta.
  • El orden de eliminación cambia la expresión y no el lenguaje. Conviene dejar para el final los estados más conectados. La expresión puede crecer del orden de 4n4^n.
  • Teorema de Kleene: un lenguaje es regular si y solo si alguna expresión regular lo describe. DFA, NFA y expresiones regulares tienen el mismo poder, con tamaños que pueden diferir exponencialmente.
  • Simular el NFA con el conjunto de estados activos cuesta O(∣w∣⋅∣R∣)O(|w| \cdot |R|) siempre. El backtracking puede tardar un tiempo exponencial: con (a∪a)∗b(\mathtt{a} \cup \mathtt{a})^*\mathtt{b} contra an\mathtt{a}^n hace 10⋅2n−410 \cdot 2^n - 4 llamadas.
  • Las referencias hacia atrás de las herramientas describen lenguajes que no son regulares, como {ww}\{ww\}. Se demuestra en la semana 4.

Ejercicios

  1. Para cada expresión, digan en palabras qué lenguaje describe, y den dos cadenas que estén y dos que no: (a) (0∪ε)1∗(\mathtt{0} \cup \varepsilon)\mathtt{1}^*; (b) (01)∗∪(10)∗(\mathtt{01})^* \cup (\mathtt{10})^*; (c) 0∗(10∗10∗)∗\mathtt{0}^*(\mathtt{10}^*\mathtt{10}^*)^*; (d) (0∪1)∗0(0∪1)(0∪1)(\mathtt{0} \cup \mathtt{1})^*\mathtt{0}(\mathtt{0} \cup \mathtt{1})(\mathtt{0} \cup \mathtt{1}). Comprueben con build/regex_lang.
  2. Dibujen el árbol de a∪bc∗\mathtt{a} \cup \mathtt{b}\mathtt{c}^*, de (a∪b)c∗(\mathtt{a} \cup \mathtt{b})\mathtt{c}^* y de (a∪bc)∗(\mathtt{a} \cup \mathtt{bc})^*, y escriban cada una con todos sus paréntesis. Den una cadena que esté en el lenguaje de la primera y no en el de la segunda, y una que esté en el de la tercera y en ninguna de las otras dos. Comprueben con build/regex_tree.
  3. Escriban una expresión regular para cada lenguaje sobre {0,1}\{\mathtt{0}, \mathtt{1}\}: (a) las cadenas con un número de ceros múltiplo de 3; (b) las que tienen al menos dos unos; (c) las que empiezan y terminan con el mismo símbolo; (d) las que no contienen 00\mathtt{00}; (e) las de longitud impar. Para cada una, prueben con build/regex_lang y busquen a mano una cadena que deba estar y otra que no.
  4. Digan cuáles de estas igualdades valen para todas las expresiones RR y SS. Demuestren las que valen y den un contraejemplo de las que no: (a) (R∪S)∗=R∗∪S∗(R \cup S)^* = R^* \cup S^*; (b) (R∗S∗)∗=(R∪S)∗(R^*S^*)^* = (R \cup S)^*; (c) (RS)∗R=R(SR)∗(RS)^*R = R(SR)^*; (d) R∗R=RR∗R^*R = RR^*; (e) (R∪ε)∗=R∗(R \cup \varepsilon)^* = R^*; (f) R(S∪∅)=RS∪∅∗R(S \cup \emptyset) = RS \cup \emptyset^*.
  5. Un estudiante propone (00∪1)∗(\mathtt{00} \cup \mathtt{1})^* para las cadenas con un número par de ceros. ¿Describe de más o de menos? Den la cadena más corta en la que falla, y comprueben con build/regex_diff '(00|1)*' '(1|01*0)*'. Después demuestren por doble inclusión que (1∪01∗0)∗(\mathtt{1} \cup \mathtt{0}\mathtt{1}^*\mathtt{0})^* describe exactamente ese lenguaje.
  6. Conviertan (ab∪a)∗(\mathtt{ab} \cup \mathtt{a})^* en un NFA con la construcción de Thompson, a mano: dibujen las piezas en el orden en que se arman y numeren los estados como lo hace el programa. Comparen con machines/ab_or_a_star.nfa. Después sigan aba\mathtt{aba} y abb\mathtt{abb} anotando los estados activos, y comprueben con build/run_nfa.
  7. ¿Cuántos estados tiene el NFA de Thompson de (0∪1)∗1(0∪1)(0∪1)(\mathtt{0} \cup \mathtt{1})^*\mathtt{1}(\mathtt{0} \cup \mathtt{1})(\mathtt{0} \cup \mathtt{1})? Calcúlenlo con la fórmula antes de construirlo. Den una expresión de tamaño nn cuyo NFA de Thompson tenga exactamente n+1n + 1 estados, y otra cuyo NFA tenga 2n2n.
  8. Eliminen los estados del DFA de machines/even_ones.dfa en los dos órdenes posibles, a mano, escribiendo en cada paso quién entra, quién sale y cuál es el ciclo. Comprueben con build/eliminate. Después expliquen con palabras por qué las dos expresiones describen el mismo lenguaje.
  9. Diseñen un DFA para las cadenas sobre {a,b}\{\mathtt{a}, \mathtt{b}\} con un número par de letras a\mathtt{a} y un número impar de letras b\mathtt{b}. Escríbanlo en formato .dfa, obtengan una expresión regular con build/orders y quédense con la más corta. ¿Qué estado se elimina al final en ella? ¿Habrían podido escribir esa expresión directamente?
  10. Demuestren que la clase de los lenguajes regulares es cerrada bajo reverso usando solo expresiones regulares: definan por casos, sobre la estructura de RR, una expresión RrevR^{\mathrm{rev}}, y demuestren por inducción sobre la estructura que L(Rrev)={ wR:w∈L(R) }L(R^{\mathrm{rev}}) = \{\, w^R : w \in L(R) \,\}. ¿En qué caso se usa que (uv)R=vRuR(uv)^R = v^Ru^R? Comparen con la construcción sobre NFA de la semana pasada.
  11. En la demostración de la eliminación de estados, ¿dónde se usa que qkq_k no es qiniq_{\text{ini}} ni qfinq_{\text{fin}}? Den un GNFA de tres estados en el que, si se olvida el ciclo de qkq_k al eliminarlo, el autómata resultante acepta menos cadenas, y digan una cadena que se pierde. ¿Puede el olvido hacer que acepte más?
  12. Para programar. Agreguen al parser de regex.h los operadores + y ? de las herramientas, como abreviaturas: R+ se convierte en el árbol de RR∗RR^* y R? en el de R∪εR \cup \varepsilon. No agreguen casos nuevos a Kind. Escriban pruebas que comparen (01)+ con 01(01)* y 0?1 con (0|%)1, y muevan 0+1 de errors/malformed.txt a las expresiones válidas. ¿Cuántos estados tiene el NFA de Thompson de R+ si el de R tiene mm?
  13. Para programar. Con backtrack.h, midan las llamadas para (a∗)∗b(\mathtt{a}^*)^*\mathtt{b} contra an\mathtt{a}^n, con nn de 1 a 20. ¿Cómo crecen? Encuentren la recurrencia. Después modifiquen el buscador para que recuerde las parejas (nodo, posición) desde las que ya fracasó y no las vuelva a probar. ¿Cuántas parejas distintas hay? ¿Qué cota da eso para el número de llamadas? Comparen esa cota con la de la simulación del NFA.