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

Apuntes · Capítulo 1Lenguajes regulares

Lenguajes y autómatas finitos

Lenguajes y autómatas finitos

En Análisis y Diseño de Algoritmos resolvieron problemas: dado un grafo, el camino más corto; dado un arreglo, el k-ésimo menor. El curso terminó con una sospecha incómoda. Para algunos problemas, como colorear un grafo con tres colores, nadie conoce un algoritmo rápido, y tampoco nadie ha demostrado que no exista. Este curso va al fondo de esa sospecha, y para eso tiene que empezar más atrás, con tres preguntas.

  • ¿Qué es calcular? Hasta ahora “algoritmo” fue algo que se reconoce al verlo: pseudocódigo, un programa en C++. Para demostrar que un problema no tiene algoritmo, eso no alcanza. Hay que decir con precisión matemática qué es una máquina que calcula, y recién entonces se puede razonar sobre todas las máquinas posibles a la vez.
  • ¿Qué no se puede calcular? Hay problemas bien definidos, con respuesta sí o no para cada entrada, que ningún programa resuelve, por más tiempo y memoria que tenga. No es que nadie haya encontrado el programa: se demuestra que no existe. El más famoso pregunta si un programa dado termina con una entrada dada.
  • ¿Qué cuesta demasiado? Entre los problemas que sí se pueden resolver, algunos parecen exigir un tiempo que crece exponencialmente con la entrada. Aquí están los problemas NP-completos que conocieron en Algoritmos, y la pregunta abierta más importante del área: si P es igual a NP.

El camino va de la máquina más simple a la más general. Cada modelo se define, se programa, y se le busca el límite: algo que no puede hacer, con su demostración. Son cuatro partes.

Parte Semanas El modelo Su límite
1. Lenguajes regulares 1 a 4 Autómatas finitos: una cantidad fija de memoria No pueden contar sin tope
2. Lenguajes libres de contexto 5 y 6 Gramáticas y autómatas con una pila No pueden comparar tres cantidades
3. Computabilidad 7 y 9 a 11 Máquinas de Turing: memoria sin límite Hay problemas que ninguna resuelve
4. Complejidad 12 a 15 Máquinas de Turing con tiempo y espacio medidos Lo que cuesta demasiado, y lo que sigue abierto
Cinco recuadros, uno dentro de otro. El de afuera, punteado, es el de todos los lenguajes sobre Σ, con la nota de que hay más lenguajes que programas y a la mayoría no la reconoce ninguna máquina. Dentro están los reconocibles: Parte 3, semanas 7 y 9 a 11, máquinas de Turing, que pueden no terminar; su ejemplo es la pregunta de si un programa termina con una entrada. Dentro, los decidibles: Parte 3, máquinas de Turing que siempre terminan, y Parte 4, semanas 12 a 15, a qué costo; su ejemplo es aⁿbⁿcⁿ, comparar tres cantidades. Dentro, los libres de contexto: Parte 2, semanas 5 y 6, gramáticas y autómatas con una pila; su ejemplo es 0ⁿ1ⁿ, contar sin tope. En el centro, los regulares: Parte 1, semanas 1 a 4, autómatas finitos con una cantidad fija de memoria; su ejemplo es la cantidad par de unosCinco recuadros, uno dentro de otro. El de afuera, punteado, es el de todos los lenguajes sobre Σ, con la nota de que hay más lenguajes que programas y a la mayoría no la reconoce ninguna máquina. Dentro están los reconocibles: Parte 3, semanas 7 y 9 a 11, máquinas de Turing, que pueden no terminar; su ejemplo es la pregunta de si un programa termina con una entrada. Dentro, los decidibles: Parte 3, máquinas de Turing que siempre terminan, y Parte 4, semanas 12 a 15, a qué costo; su ejemplo es aⁿbⁿcⁿ, comparar tres cantidades. Dentro, los libres de contexto: Parte 2, semanas 5 y 6, gramáticas y autómatas con una pila; su ejemplo es 0ⁿ1ⁿ, contar sin tope. En el centro, los regulares: Parte 1, semanas 1 a 4, autómatas finitos con una cantidad fija de memoria; su ejemplo es la cantidad par de unos
El mapa del curso: cada clase de lenguajes contiene a la anterior. El ejemplo de cada recuadro es un lenguaje que el recuadro de adentro no alcanza.

Esta semana tiene dos mitades. En la primera fijamos el vocabulario de todo el curso: cadenas y lenguajes. Todo problema con respuesta sí o no se va a escribir como un lenguaje, y toda máquina se va a juzgar por el lenguaje que reconoce. En la segunda aparece la primera máquina, el autómata finito determinista: lee su entrada una sola vez, de izquierda a derecha, y solo recuerda en cuál de una cantidad fija de estados está. Es poco, y aun así alcanza para mucho. Aprenderemos a diseñar uno, a demostrar que hace lo que decimos, y a combinar dos en uno solo con la construcción del producto.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Alfabetos y cadenas y Lenguajes. Antes de la sesión B, Máquinas con memoria fija. Con eso llegan con el vocabulario y con el primer autómata ya visto.

En clase: Sesión A, de Alfabetos y cadenas a Hay más lenguajes que programas. Sesión B, de Máquinas con memoria fija a Complemento.

Después de clase: el Resumen y los Ejercicios, para repasar. Antes del laboratorio, La definición formal de un DFA otra vez y El código de la semana. Para ampliar, Lo que un DFA no puede hacer y las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, capítulo 0, la parte sobre cadenas y lenguajes, y sec. 1.1 (Finite Automata). Erickson, Models of Computation, notas 1 (Strings) y 3 (Finite-state automata). Son apoyo: estos apuntes se pueden estudiar solos.

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

Alfabetos y cadenas

Un alfabeto (alphabet) es un conjunto finito y no vacío. Sus elementos se llaman símbolos (symbols). Lo escribimos Σ\Sigma. Algunos alfabetos que usaremos:

  • Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\}, el alfabeto binario. Es el de casi todos los ejemplos.
  • Σ={a,b}\Sigma = \{\mathtt{a}, \mathtt{b}\}, cuando conviene que los símbolos no parezcan números.
  • Σ={a,b,…,z}\Sigma = \{\mathtt{a}, \mathtt{b}, \ldots, \mathtt{z}\}, o el conjunto de los caracteres ASCII, cuando la cadena es un texto.

Qué son los símbolos no importa. Importa que sean finitos y que se puedan distinguir uno de otro.

Una cadena (string) sobre Σ\Sigma es una secuencia finita de símbolos de Σ\Sigma, escritos uno detrás de otro: 0110\mathtt{0110} es una cadena sobre {0,1}\{\mathtt{0}, \mathtt{1}\}, y abba\mathtt{abba} es una cadena sobre {a,b}\{\mathtt{a}, \mathtt{b}\}. Usaremos las letras del final del abecedario, uu, vv, ww, xx, yy, zz, para nombrar cadenas, y las del principio, aa, bb, cc, para nombrar símbolos.

La longitud de una cadena ww es la cantidad de símbolos que tiene, contando las repeticiones. Se escribe ∣w∣|w|. Así, ∣0110∣=4|\mathtt{0110}| = 4 y ∣abba∣=4|\mathtt{abba}| = 4.

Hay exactamente una cadena de longitud 0: la que no tiene ningún símbolo. Se llama cadena vacía (empty string) y se escribe ε\varepsilon. La letra ε\varepsilon no es un símbolo del alfabeto: es el nombre que le damos a esa cadena para poder escribirla, porque de otro modo no se vería en el papel. En C++ es "".

El conjunto de todas las cadenas sobre Σ\Sigma se escribe Σ∗\Sigma^*. Tiene a ε\varepsilon, a cada símbolo como cadena de longitud 1, y sigue sin fin. El programa strings_demo las lista en un orden que usaremos mucho: primero las más cortas y, entre las de igual longitud, en el orden del alfabeto.

$ build/strings_demo
Σ = {0, 1}. Las cadenas de Σ* con longitud a lo sumo 3, en orden:
  ε 0 1 00 01 10 11 000 001 010 011 100 101 110 111

 n   cadenas de longitud n   cadenas de longitud ≤ n
 0                 1                        1
 1                 2                        3
 2                 4                        7
 3                 8                       15
 4                16                       31
 5                32                       63
 6                64                      127
 7               128                      255
 8               256                      511
 9               512                     1023
10              1024                     2047

El programa imprime además un ejemplo de prefijos y sufijos, que está unas líneas más abajo. Las dos columnas de la tabla se explican contando. Una cadena de longitud nn se arma eligiendo nn veces un símbolo, y cada elección tiene ∣Σ∣|\Sigma| opciones: hay ∣Σ∣n|\Sigma|^n cadenas de longitud nn. Con Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\} son 2n2^n, y de longitud a lo sumo nn son

1+2+4+⋯+2n=2n+1−1.1 + 2 + 4 + \cdots + 2^n = 2^{n+1} - 1.

Para n=0n = 0 la fórmula da 20=12^0 = 1: la cadena vacía.

Dos cosas sobre Σ∗\Sigma^* que conviene tener claras desde ahora:

  • Σ∗\Sigma^* es infinito, pero cada una de sus cadenas es finita. No existen cadenas infinitas en este curso.
  • Σ∗\Sigma^* se puede listar: en el orden de arriba, cada cadena aparece en alguna posición finita. La cadena 101\mathtt{101} es la número 13 si contamos desde 1. Esta observación vuelve al final de la sesión.

Concatenación

La concatenación (concatenation) de dos cadenas uu y vv es la cadena que resulta de escribir vv a continuación de uu. Se escribe uvuv. Si u=abu = \mathtt{ab} y v=bav = \mathtt{ba}, entonces uv=abbauv = \mathtt{abba} y vu=baabvu = \mathtt{baab}.

  • La cadena vacía es el elemento neutro: εw=wε=w\varepsilon w = w\varepsilon = w, para toda ww.
  • Es asociativa: (uv)w=u(vw)(uv)w = u(vw). Por eso se escribe uvwuvw sin paréntesis.
  • No es conmutativa: abba≠baab\mathtt{abba} \neq \mathtt{baab}.

Repetir una cadena kk veces se escribe con un exponente: wk=ww⋯ww^k = ww \cdots w, con kk copias. Así, (ab)3=ababab(\mathtt{ab})^3 = \mathtt{ababab} y 0312=00011\mathtt{0}^3\mathtt{1}^2 = \mathtt{00011}. Por convención w0=εw^0 = \varepsilon, igual que un producto sin factores vale 1. El reverso (reversal) de ww, que se escribe wRw^R, es la misma cadena leída de derecha a izquierda: (abb)R=bba(\mathtt{abb})^R = \mathtt{bba}.

Error común. Leer 03\mathtt{0}^3 como el número cero al cubo. En este curso los símbolos no son números: 03\mathtt{0}^3 es la cadena 000\mathtt{000}, y 0312\mathtt{0}^3\mathtt{1}^2 tiene longitud 5.

Prefijos, sufijos y subcadenas

Sean xx y ww dos cadenas.

  • xx es un prefijo (prefix) de ww si w=xyw = xy para alguna cadena yy: ww empieza con xx.
  • xx es un sufijo (suffix) de ww si w=yxw = yx para alguna cadena yy: ww termina con xx.
  • xx es una subcadena (substring) de ww si w=yxzw = yxz para algunas cadenas yy, zz: xx aparece dentro de ww, con sus símbolos seguidos.

En las tres definiciones, las cadenas yy, zz pueden ser vacías. Por eso ε\varepsilon es prefijo, sufijo y subcadena de toda cadena, y toda cadena lo es de sí misma. Y todo prefijo y todo sufijo es una subcadena.

w = abba, |w| = 4
prefijos (5):   {ε, a, ab, abb, abba}
sufijos (5):    {ε, a, ba, bba, abba}
subcadenas (9): {ε, a, b, ab, ba, bb, abb, bba, abba}

Estas son las últimas líneas que imprime build/strings_demo. Una cadena de longitud nn tiene exactamente n+1n + 1 prefijos, uno por cada longitud de 0 a nn, y n+1n + 1 sufijos. Subcadenas distintas tiene a lo sumo n(n+1)/2+1n(n + 1)/2 + 1: una por cada par de posiciones de inicio y fin, más la vacía. Para n=4n = 4 el máximo es 11, y abba\mathtt{abba} tiene 9 porque algunas se repiten: la subcadena a\mathtt{a} aparece dos veces y la b\mathtt{b} también.

“Subcadena” exige que los símbolos estén seguidos. La cadena aa\mathtt{aa} no es subcadena de abba\mathtt{abba}, aunque sus dos símbolos aparezcan en ese orden.

En C++. Una cadena es un std::string, y la cadena vacía es "", con size() igual a 0. La concatenación es u + v, un prefijo es w.substr(0, k) y un sufijo es w.substr(k). Un símbolo es un char. Las funciones prefixes, suffixes y substrings de languages.h son las tres definiciones de arriba, escritas con substr.

Inducción sobre cadenas

Casi todas las demostraciones de las primeras semanas son por inducción sobre la longitud de una cadena. La inducción es la de Matemática Discreta. Lo único nuevo es en qué se apoya: toda cadena no vacía se arma agregando un símbolo a una cadena más corta.

Dicho con precisión, una cadena ww sobre Σ\Sigma es de una de dos formas:

  • w=εw = \varepsilon, o
  • w=xaw = xa, donde xx es una cadena sobre Σ\Sigma y aa es un símbolo de Σ\Sigma.

En el segundo caso, xx y aa quedan determinados por ww: aa es el último símbolo y xx es todo lo anterior. Esto permite definir funciones sobre cadenas por casos, igual que una función recursiva tiene un caso base y uno recursivo. La longitud y la concatenación, que arriba describimos con palabras, quedan así:

∣ε∣=0u⋅ε=u∣xa∣=∣x∣+1u⋅(xa)=(u⋅x)a\begin{aligned} |\varepsilon| &= 0 & \qquad u \cdot \varepsilon &= u \\ |xa| &= |x| + 1 & \qquad u \cdot (xa) &= (u \cdot x)a \end{aligned}

El punto de u⋅vu \cdot v es la concatenación, que aquí escribimos de forma explícita para que se vea qué se está definiendo. La segunda columna dice: para concatenar uu con una cadena que termina en aa, se concatena uu con lo anterior y se agrega aa al final.

Con las definiciones escritas así, las propiedades se demuestran y no solo se creen. Un ejemplo corto, que además fija el esquema que seguiremos todo el curso.

Afirmación. Para todas las cadenas uu y vv, ∣uv∣=∣u∣+∣v∣|uv| = |u| + |v|.

Demostración. Por inducción sobre la longitud de vv. La cadena uu queda fija, cualquiera.

Caso base: ∣v∣=0|v| = 0, es decir, v=εv = \varepsilon. Entonces uv=u⋅ε=uuv = u \cdot \varepsilon = u por la definición de concatenación, y ∣uv∣=∣u∣=∣u∣+0=∣u∣+∣ε∣|uv| = |u| = |u| + 0 = |u| + |\varepsilon|.

Hipótesis de inducción: la afirmación vale para toda cadena vv de longitud nn.

Paso inductivo: sea vv una cadena de longitud n+1n + 1. Como no es vacía, v=xav = xa con ∣x∣=n|x| = n. Entonces:

∣uv∣=∣u⋅(xa)∣=∣(u⋅x)a∣definicioˊn de concatenacioˊn=∣u⋅x∣+1definicioˊn de longitud=∣u∣+∣x∣+1hipoˊtesis de induccioˊn, porque ∣x∣=n=∣u∣+∣xa∣definicioˊn de longitud=∣u∣+∣v∣\begin{aligned} |uv| &= |u \cdot (xa)| \\ &= |(u \cdot x)a| && \text{definición de concatenación} \\ &= |u \cdot x| + 1 && \text{definición de longitud} \\ &= |u| + |x| + 1 && \text{hipótesis de inducción, porque } |x| = n \\ &= |u| + |xa| && \text{definición de longitud} \\ &= |u| + |v| \end{aligned}

Con eso la afirmación vale para todas las cadenas vv, de cualquier longitud. ∎

La afirmación es obvia, y por eso sirve de ejemplo: lo que interesa es la forma. El caso base es la cadena vacía. El paso inductivo le quita el último símbolo a la cadena, aplica la hipótesis a lo que queda y vuelve a poner el símbolo. Cuando demostremos que un autómata es correcto, el paso inductivo será exactamente el momento en que el autómata lee un símbolo más.

Error común. Empezar la inducción en las cadenas de longitud 1. El caso base es ε\varepsilon, de longitud 0. Si se olvida, la demostración no dice nada sobre la cadena vacía, y la cadena vacía es justo la entrada con la que más programas y más autómatas fallan.

Lenguajes

Un lenguaje (language) sobre Σ\Sigma es un conjunto de cadenas sobre Σ\Sigma. Es decir, un subconjunto de Σ∗\Sigma^*. Cualquiera: no se le pide ninguna estructura ni ningún significado.

Algunos lenguajes sobre Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\}:

  • {0,01,111}\{\mathtt{0}, \mathtt{01}, \mathtt{111}\}, un lenguaje finito con tres cadenas.
  • { w:w tiene una cantidad par de unos }\{\, w : w \text{ tiene una cantidad par de unos} \,\}. Tiene a ε\varepsilon, a 0\mathtt{0}, a 11\mathtt{11}, a 0110\mathtt{0110}, y no a 1\mathtt{1} ni a 1101\mathtt{1101}.
  • { w:w termina en 01 }\{\, w : w \text{ termina en } \mathtt{01} \,\}.
  • { 0n1n:n≥0 }={ε,01,0011,000111,…}\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} = \{\varepsilon, \mathtt{01}, \mathtt{0011}, \mathtt{000111}, \ldots\}: algunos ceros seguidos de la misma cantidad de unos.
  • { w:w es un nuˊmero primo en binario }={10,11,101,111,1011,…}\{\, w : w \text{ es un número primo en binario} \,\} = \{\mathtt{10}, \mathtt{11}, \mathtt{101}, \mathtt{111}, \mathtt{1011}, \ldots\}.
  • Σ∗\Sigma^*, el lenguaje de todas las cadenas.
  • ∅\emptyset, el lenguaje que no tiene ninguna.

Salvo el primero y el último, todos son infinitos, y ese es el caso normal. Un lenguaje infinito no se puede dar con una lista: se da con una condición que dice qué cadenas están. Todo el curso gira alrededor de una pregunta sobre esas condiciones: dado un lenguaje LL y una cadena ww, ¿se puede saber mecánicamente si w∈Lw \in L? ¿Con qué máquina? ¿Con cuánto esfuerzo?

Hay dos lenguajes pequeños que se confunden todo el tiempo.

  • ∅\emptyset es el lenguaje vacío: no tiene ninguna cadena. ∣∅∣=0|\emptyset| = 0.
  • {ε}\{\varepsilon\} es el lenguaje que tiene una sola cadena, la cadena vacía. ∣{ε}∣=1|\{\varepsilon\}| = 1.

Y ε\varepsilon, sin llaves, no es un lenguaje: es una cadena. Los tres objetos son de tipos distintos, y en C++ se ve enseguida.

En C++. Si un lenguaje finito es un std::set<std::string>, entonces ∅\emptyset es {}, un conjunto con size() == 0, y {ε}\{\varepsilon\} es {""}, un conjunto con size() == 1 cuyo único elemento es un std::string con size() == 0. La cadena ε\varepsilon es "", que ni siquiera es del mismo tipo que los otros dos.

Error común. Confundir ε\varepsilon, la cadena sin símbolos, con ∅\emptyset, el lenguaje sin cadenas. Una caja vacía no es lo mismo que no tener caja. “El autómata acepta ε\varepsilon” dice que una cadena concreta, la vacía, está en su lenguaje. “El lenguaje del autómata es ∅\emptyset” dice que no acepta ninguna cadena, tampoco la vacía. La sección siguiente muestra que las dos se comportan distinto en cada operación.

Operaciones sobre lenguajes

Los lenguajes son conjuntos, así que tienen las operaciones de conjuntos. Sean AA y BB lenguajes sobre Σ\Sigma.

  • Unión: A∪B={ w:w∈A o w∈B }A \cup B = \{\, w : w \in A \text{ o } w \in B \,\}.
  • Intersección: A∩B={ w:w∈A y w∈B }A \cap B = \{\, w : w \in A \text{ y } w \in B \,\}.
  • Complemento: el complemento de AA es Σ∗−A={ w∈Σ∗:w∉A }\Sigma^* - A = \{\, w \in \Sigma^* : w \notin A \,\}. El complemento siempre es respecto de Σ∗\Sigma^*: hay que saber cuál es el alfabeto. Lo escribimos “el complemento de AA” o, en las fórmulas, A‾\overline{A}.

Y tienen dos operaciones propias, que vienen de la concatenación de cadenas.

  • Concatenación: AB={ uv:u∈A y v∈B }AB = \{\, uv : u \in A \text{ y } v \in B \,\}. Todas las maneras de pegar una cadena de AA con una de BB, en ese orden.
  • Potencias y estrella: A0={ε}A^0 = \{\varepsilon\}, Ak+1=AkAA^{k+1} = A^kA, y la estrella de Kleene (Kleene star) es la unión de todas las potencias:
A∗=A0∪A1∪A2∪A3∪⋯A^* = A^0 \cup A^1 \cup A^2 \cup A^3 \cup \cdots

Una cadena está en A∗A^* si se puede partir en cero o más trozos, cada uno de AA. Cero trozos da la cadena vacía, así que ε\varepsilon está en A∗A^* siempre, sea AA lo que sea. La notación Σ∗\Sigma^* es un caso de esta: las cadenas que se parten en trozos de un símbolo, que son todas.

El programa languages_demo calcula estas operaciones con dos lenguajes finitos. La estrella y el complemento son infinitos, así que solo muestra sus cadenas más cortas.

$ build/languages_demo
A = {0, 01}    B = {ε, 1, 01}

A ∪ B = {ε, 0, 1, 01}
A ∩ B = {01}
AB    = {0, 01, 001, 011, 0101}
BA    = {0, 01, 10, 010, 101, 0101}
A²    = {00, 001, 010, 0101}
A*, hasta longitud 3:              {ε, 0, 00, 01, 000, 001, 010}
complemento de A, hasta longitud 2: {ε, 1, 00, 10, 11}

|∅| = 0    |{ε}| = 1
∅A   = ∅
{ε}A = {0, 01}
∅ ∪ A = {0, 01}
∅*   = {ε}
{ε}* = {ε}
∅⁰   = {ε}    ∅¹ = ∅

Vale la pena mirar tres cosas en esa salida.

ABAB tiene 5 cadenas y no 6. AA tiene 2 cadenas y BB tiene 3, así que hay 6 maneras de elegir uu y vv. Pero dos de ellas dan la misma cadena: 0⋅1=01\mathtt{0} \cdot \mathtt{1} = \mathtt{01} y 01⋅ε=01\mathtt{01} \cdot \varepsilon = \mathtt{01}. En general ∣AB∣≤∣A∣⋅∣B∣|AB| \leq |A| \cdot |B|, y la igualdad puede fallar.

AB≠BAAB \neq BA. La cadena 10\mathtt{10} está en BABA, porque 10=1⋅0\mathtt{10} = \mathtt{1} \cdot \mathtt{0}, y no está en ABAB, porque toda cadena de ABAB empieza con 0\mathtt{0}.

∅\emptyset y {ε}\{\varepsilon\} hacen cosas opuestas. Concatenar con {ε}\{\varepsilon\} no cambia nada: {ε}A=A\{\varepsilon\}A = A, porque εu=u\varepsilon u = u. Concatenar con ∅\emptyset lo destruye todo: ∅A=∅\emptyset A = \emptyset, porque para formar uvuv hace falta elegir una uu de ∅\emptyset, y no hay ninguna. En cambio, en la unión es ∅\emptyset el que no cambia nada. Es la misma relación que hay entre el 1 y el 0 en la multiplicación: {ε}\{\varepsilon\} hace de 1 y ∅\emptyset hace de 0.

Y la línea más rara: ∅∗={ε}\emptyset^* = \{\varepsilon\}. Sale de la definición sin forzar nada. La potencia ∅0\emptyset^0 es {ε}\{\varepsilon\} por definición, y todas las demás potencias son vacías, porque ∅k+1=∅k∅=∅\emptyset^{k+1} = \emptyset^k\emptyset = \emptyset. La unión de {ε}\{\varepsilon\} con muchos conjuntos vacíos es {ε}\{\varepsilon\}. Con palabras: la única cadena que se puede partir en cero o más trozos tomados de ∅\emptyset es la que se parte en cero trozos.

Idea clave. Un lenguaje es un conjunto de cadenas, y nada más. ∅\emptyset no tiene cadenas, {ε}\{\varepsilon\} tiene una, y Σ∗\Sigma^* las tiene todas. Las operaciones que importan son cinco: unión, intersección, complemento, concatenación y estrella.

De problemas a lenguajes

Un problema de decisión (decision problem) es un problema en el que cada entrada tiene respuesta sí o no. ¿Es nn un número primo? ¿Es este grafo conexo? ¿Tiene esta fórmula una asignación que la haga verdadera? ¿Compila este programa?

Para una computadora, la entrada de un problema siempre es una cadena: los bytes de un archivo, lo que llega por la entrada estándar. Así que un problema de decisión parte a Σ∗\Sigma^* en dos: las cadenas con respuesta sí y las demás. Con eso basta para describirlo.

Idea clave. Un problema de decisión es un lenguaje: el conjunto de las entradas cuya respuesta es sí. Resolver el problema es decidir, dada una cadena, si está en ese lenguaje.

“¿Es nn primo?” es el lenguaje

PRIMES={ w∈{0,1}∗:w es la representacioˊn en binario de un nuˊmero primo }\mathrm{PRIMES} = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : w \text{ es la representación en binario de un número primo} \,\}

y preguntar si 11 es primo es preguntar si 1011∈PRIMES\mathtt{1011} \in \mathrm{PRIMES}. Al pasar de un problema a un lenguaje hay que tomar decisiones que normalmente no se dicen:

  • Cómo se escribe la entrada. Aquí, el número en binario. Un grafo se puede escribir como su lista de aristas, con algún separador. Cualquier objeto finito se puede escribir como cadena, y más adelante escribiremos ⟨G⟩\langle G \rangle para “la cadena que representa a GG”. Mientras la representación sea razonable, cuál se elija no cambia lo que se puede calcular. Sí puede cambiar cuánto cuesta, y eso se verá en la parte de complejidad.
  • Qué pasa con las cadenas mal formadas. Si la entrada debía ser un grafo y llega una cadena que no representa ninguno, la respuesta es no: esa cadena no está en el lenguaje. No hay un tercer caso.
  • Los detalles de la representación. ¿Se permiten ceros a la izquierda? ¿Qué número representa ε\varepsilon? Cada elección da un lenguaje distinto, aunque el problema “sea el mismo”. Cuando importe, lo diremos.

Por qué basta estudiar problemas de decisión

Muchos problemas reales no son de sí o no: piden un número, un camino, un programa traducido. Aun así, el curso entero trabaja con problemas de decisión, por tres razones.

Son lo más simple que ya es difícil. Si no se puede decidir si existe un camino de costo a lo sumo kk, tampoco se puede hallar el camino más barato: quien lo halla, responde de paso la pregunta de sí o no. Un resultado de imposibilidad para la versión de decisión vale entonces para la versión completa. Como este curso trata sobre todo de límites, la versión de decisión es la que conviene.

Casi siempre se puede volver. Con un programa que decide, se suele reconstruir la respuesta completa haciéndole varias preguntas. Si f(x)f(x) es un número, se pregunta “¿el bit ii de f(x)f(x) es 1?” para cada ii, y cada una de esas es una pregunta de sí o no sobre la entrada (x,i)(x, i). Lo vieron en Algoritmos con los problemas de optimización y su versión con umbral.

Dan un solo tipo de objeto. Si todo problema es un lenguaje, se pueden comparar problemas que no se parecen en nada, clasificarlos por la máquina que hace falta para decidirlos, y aplicarles las mismas operaciones.

Hay más lenguajes que programas

Antes de construir ninguna máquina ya se puede responder, a grandes rasgos, la segunda pregunta del curso. El argumento es de puro conteo, y por ahora va sin formalizar: qué es exactamente un “programa” y qué es “decidir” se precisa en las semanas 7 y 9, donde este mismo argumento vuelve completo.

Los programas se pueden listar. Un programa en C++ es un archivo de texto: una cadena sobre el alfabeto de los caracteres. Vimos que todas las cadenas sobre un alfabeto se pueden poner en una lista, primero las más cortas. Si de esa lista dejamos solo las cadenas que son programas, queda una lista de todos los programas: el primero, el segundo, el tercero, sin fin, y cada programa aparece en alguna posición.

Cada programa decide a lo sumo un lenguaje: el de las entradas con las que responde sí. Entonces los lenguajes que algún programa decide también se pueden listar: L1L_1 es el del primer programa, L2L_2 el del segundo, y así.

Los lenguajes no se pueden listar. Supongamos que alguien nos da una lista cualquiera de lenguajes sobre {0,1}\{\mathtt{0}, \mathtt{1}\}: L1,L2,L3,…L_1, L_2, L_3, \ldots Vamos a construir un lenguaje que no está en ella. Listamos también las cadenas en el orden de siempre: s1=εs_1 = \varepsilon, s2=0s_2 = \mathtt{0}, s3=1s_3 = \mathtt{1}, s4=00s_4 = \mathtt{00}, … Y definimos

D={ si:si∉Li }D = \{\, s_i : s_i \notin L_i \,\}

Es decir, para decidir si la cadena número ii entra en DD, miramos el lenguaje número ii y hacemos lo contrario. Entonces DD no puede ser L1L_1, porque s1s_1 está en exactamente uno de los dos. Tampoco puede ser L2L_2, porque difieren en s2s_2. En general D≠LiD \neq L_i para todo ii, porque difieren en sis_i. El lenguaje DD no está en la lista.

Juntando las dos mitades: si la lista es la de los lenguajes que algún programa decide, DD es un lenguaje que ningún programa decide.

Hay una forma de sentir la diferencia de tamaños con números pequeños. Un lenguaje se arma decidiendo, para cada cadena, si entra o no. Solo con las 7 cadenas binarias de longitud a lo sumo 2 ya hay 27=1282^7 = 128 lenguajes distintos. Con las 15 de longitud a lo sumo 3, hay 215=32 7682^{15} = 32\,768. Los lenguajes son todas las maneras de elegir un subconjunto de Σ∗\Sigma^*, y eso es muchísimo más que Σ∗\Sigma^*.

El argumento tiene un defecto que es justo lo que hace interesante al resto del curso: no dice cuál problema no se puede resolver. El lenguaje DD depende de una lista y no se parece a nada que alguien quiera calcular. Podría ser que todos los problemas con una descripción razonable sí tengan programa. En la semana 9 veremos que no: hay problemas concretos, naturales y útiles que ningún programa decide.

Con esto termina la primera mitad. Tenemos el vocabulario, y sabemos que hay lenguajes fuera del alcance de cualquier máquina. Ahora empezamos por el otro extremo: la máquina más simple, y los lenguajes que sí alcanza.

Máquinas con memoria fija

Piensen en la puerta automática de un supermercado, de las que giran hacia adentro. Tiene dos sensores: uno delante, que detecta a quien quiere entrar, y otro detrás, que detecta si hay alguien en el espacio que la puerta barre al abrirse. El controlador de la puerta es una computadora muy pequeña. No guarda una historia de lo que pasó ni cuenta personas. En cada instante solo sabe una cosa, si la puerta está cerrada o abierta, y con eso y la señal de los sensores decide qué hacer:

Estado ninguno delante detrás ambos
cerrada cerrada abierta cerrada cerrada
abierta cerrada abierta abierta abierta

La tabla se lee por filas. Si la puerta está cerrada y solo hay alguien delante, se abre. Si además hay alguien detrás, se queda cerrada, para no golpearlo. Si está abierta, se queda abierta mientras haya alguien en cualquiera de los dos lados, y se cierra cuando no hay nadie. Toda la “memoria” del controlador es un bit: en cuál de las dos filas está.

Un torniquete es otra máquina igual. Tiene dos estados, bloqueado y libre, y le pueden pasar dos cosas: que entre una moneda o que alguien empuje. Con una moneda queda libre. Con un empujón, si estaba libre deja pasar y vuelve a bloquearse, y si estaba bloqueado no pasa nada. Si a la moneda la llamamos m\mathtt{m} y al empujón e\mathtt{e}, lo que le pasa al torniquete durante el día es una cadena sobre {m,e}\{\mathtt{m}, \mathtt{e}\}, y podemos seguirla:

$ build/run_dfa machines/turnstile.dfa emme
w = emme
  bloqueado -e-> bloqueado -m-> libre -m-> libre -e-> bloqueado
  termina en bloqueado, que está en F: acepta

La línea del medio es la historia completa: el estado antes de leer nada, y el estado después de cada símbolo. La segunda moneda se perdió: el torniquete ya estaba libre y no tiene dónde anotar que le deben una pasada. Para recordar cuántas monedas entraron haría falta un estado por cada cantidad posible, y la máquina tiene dos.

La última línea habla de aceptar, y eso es lo que convierte a estas máquinas en algo que decide lenguajes. Se marcan algunos estados como de aceptación, y la máquina acepta una cadena si, después de leerla completa, queda en uno de ellos. En el archivo machines/turnstile.dfa el estado marcado es bloqueado, así que la máquina acepta exactamente las secuencias que dejan el torniquete bloqueado.

Ahora un ejemplo donde el lenguaje interesa por sí mismo.

Problema. Decidir si una cadena binaria tiene una cantidad par de unos.

Un programa normal contaría los unos y al final miraría si el contador es par. Pero el contador no hace falta: basta recordar si la cantidad de unos leídos hasta ahora es par o impar. Eso es un bit, dos estados. Al leer un 0\mathtt{0}, la paridad no cambia. Al leer un 1\mathtt{1}, cambia. Antes de leer nada hay cero unos, y cero es par.

Diagrama de estados con dos estados, par e impar. Una flecha que no sale de ningún estado entra a par: es el estado inicial. Par tiene doble círculo: es de aceptación. Par tiene un bucle con 0 y una flecha con 1 hacia impar. Impar tiene un bucle con 0 y una flecha con 1 de vuelta a par. Tres notas señalan las convenciones: la flecha que entra desde ninguna parte marca el estado inicial, el doble círculo marca el estado de aceptación, y el bucle de impar es la transición δ(impar, 0) = imparDiagrama de estados con dos estados, par e impar. Una flecha que no sale de ningún estado entra a par: es el estado inicial. Par tiene doble círculo: es de aceptación. Par tiene un bucle con 0 y una flecha con 1 hacia impar. Impar tiene un bucle con 0 y una flecha con 1 de vuelta a par. Tres notas señalan las convenciones: la flecha que entra desde ninguna parte marca el estado inicial, el doble círculo marca el estado de aceptación, y el bucle de impar es la transición δ(impar, 0) = impar
El autómata de la paridad. Un 0 deja a la máquina donde está y un 1 la cambia de estado.

Este dibujo es un diagrama de estados. Cada círculo es un estado. La flecha que entra desde ninguna parte señala el estado inicial. El doble círculo marca los estados de aceptación. Cada flecha con una etiqueta es una transición: desde este estado, con este símbolo, se pasa a aquel.

$ build/run_dfa machines/even_ones.dfa 1101 '' 0110
w = 1101
  par -1-> impar -1-> par -0-> par -1-> impar
  termina en impar, que no está en F: rechaza
w = ε
  par
  termina en par, que está en F: acepta
w = 0110
  par -0-> par -1-> impar -1-> par -0-> par
  termina en par, que está en F: acepta

Con la cadena vacía la máquina no se mueve: termina donde empezó, en par, y acepta. Es lo correcto, porque ε\varepsilon tiene cero unos.

Animación del autómata de la paridad con la cadena 1101. Arriba está la cadena, con una marca que avanza un símbolo por paso; en el medio, el diagrama, con el estado actual resaltado; abajo se va escribiendo la ejecución. Antes de leer nada, el estado actual es par. Lee 1: sigue la flecha de par a impar, δ(par, 1) = impar. Lee 1: vuelve de impar a par, δ(impar, 1) = par. Lee 0: recorre el bucle de par, δ(par, 0) = par. Lee 1: pasa a impar, δ(par, 1) = impar. La ejecución completa es par, impar, par, par, impar. Termina en impar, que no está en F, y rechazaAnimación del autómata de la paridad con la cadena 1101. Arriba está la cadena, con una marca que avanza un símbolo por paso; en el medio, el diagrama, con el estado actual resaltado; abajo se va escribiendo la ejecución. Antes de leer nada, el estado actual es par. Lee 1: sigue la flecha de par a impar, δ(par, 1) = impar. Lee 1: vuelve de impar a par, δ(impar, 1) = par. Lee 0: recorre el bucle de par, δ(par, 0) = par. Lee 1: pasa a impar, δ(par, 1) = impar. La ejecución completa es par, impar, par, par, impar. Termina en impar, que no está en F, y rechaza
La primera ejecución de la salida de arriba, paso a paso. La máquina pasa tres veces por par, pero rechaza: solo cuenta el estado en el que termina.

Idea clave. Un autómata finito lee la entrada una sola vez, de izquierda a derecha, y no puede volver atrás ni anotar nada. Todo lo que sabe de lo que ya leyó es en qué estado está. La cantidad de estados es fija: no crece con la entrada.

En la práctica. Esta forma de programar aparece cada vez que un sistema reacciona a eventos con poca memoria: el controlador de un ascensor o de un semáforo, el estado de una conexión de red (cerrada, esperando, establecida), el flujo de pantallas de un cajero. Y aparece dentro de las herramientas de texto: el analizador léxico de un compilador, que parte el código fuente en tokens, es un autómata finito.

La definición formal de un DFA

Los tres ejemplos tienen las mismas piezas: unos estados, unos símbolos, una regla para pasar de un estado a otro, un estado donde se empieza y unos estados que significan sí. La definición formal es la lista de esas piezas.

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

  1. QQ es un conjunto finito, el de los estados.
  2. Σ\Sigma es un alfabeto.
  3. δ:Q×Σ→Q\delta : Q \times \Sigma \to Q es la función de transición (transition function).
  4. q0∈Qq_0 \in Q es el estado inicial (start state).
  5. F⊆QF \subseteq Q es el conjunto de los estados de aceptación (accept states).

En este curso se usan las siglas en inglés, DFA, NFA y PDA, que son las de Sipser y las de casi toda la documentación. Los libros en español escriben AFD (autómata finito determinista), AFN (no determinista) y AP (autómata de pila). Son los mismos objetos: ténganlo presente si buscan en esas fuentes.

Cada parte de la definición dice algo que conviene leer despacio.

  • δ\delta es una función de Q×ΣQ \times \Sigma en QQ. Recibe un estado y un símbolo, y devuelve un estado: δ(par,1)=impar\delta(\mathit{par}, \mathtt{1}) = \mathit{impar}. Que sea una función quiere decir dos cosas a la vez. Está definida para todos los pares: desde cada estado sale una flecha con cada símbolo, sin excepción. Y da un solo resultado: no salen dos flechas con el mismo símbolo. De ahí la palabra determinista: el estado actual y el símbolo leído determinan el siguiente estado, sin elección. La semana próxima quitaremos esa condición.
  • Hay un solo estado inicial. Es q0q_0 por costumbre, aunque en un archivo puede llamarse como sea.
  • FF es cualquier subconjunto de QQ. Puede tener un estado, varios, todos, o ninguno: F=∅F = \emptyset es legal, y da un autómata que no acepta nada. El estado inicial puede estar en FF.
  • QQ es finito. Es la única limitación de la máquina, y todo lo que un DFA no puede hacer sale de ahí.

El autómata de la paridad, escrito como quíntupla, es M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) con Q={par,impar}Q = \{\mathit{par}, \mathit{impar}\}, Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\}, q0=parq_0 = \mathit{par}, F={par}F = \{\mathit{par}\}, y δ\delta dada por:

δ\delta 0\mathtt{0} 1\mathtt{1}
par\mathit{par} par\mathit{par} impar\mathit{impar}
impar\mathit{impar} impar\mathit{impar} par\mathit{par}

Esta es la tabla de transiciones: una fila por estado, una columna por símbolo, y en cada casilla δ(estado,sıˊmbolo)\delta(\text{estado}, \text{símbolo}). La tabla y el diagrama dicen lo mismo. Cada casilla de la tabla es una flecha del diagrama, y al revés. Lo único que la tabla no muestra es cuál es el estado inicial y cuáles son de aceptación, y por eso se anotan aparte o con marcas. El diagrama sirve para pensar, y la tabla para programar y para comprobar que no falta nada: una casilla vacía es una transición olvidada, y salta a la vista.

En el formato del curso, que está descrito en code/formats.md, la misma quíntupla es un archivo de texto con un campo por componente. Este es machines/even_ones.dfa:

# Cadenas binarias con una cantidad par de unos.
states: par impar
alphabet: 0 1
start: par
accept: par
delta:
par 0 par
par 1 impar
impar 0 impar
impar 1 par

Después de delta: va una línea por cada casilla de la tabla: estado símbolo destino. El programa show_dfa lee un archivo y lo muestra de las dos maneras:

$ build/show_dfa machines/even_ones.dfa
Q  = {par, impar}
Σ  = {0, 1}
q0 = par
F  = {par}

     δ      0      1
-> * par    par    impar
     impar  impar  par

estados alcanzables desde par: 2 de 2

En la tabla que imprime, -> marca el estado inicial y * los de aceptación.

En C++. El struct Dfa de dfa.h tiene los cinco componentes con los nombres del formato: states, alphabet, delta, start y accept. La función δ\delta es un std::map cuya clave es el par (estado, símbolo) y cuyo valor es el estado de destino, así que delta.at({"par", '1'}) es δ(par,1)\delta(\mathit{par}, \mathtt{1}). Un std::map guarda un solo valor por clave: la estructura ya impide que haya dos flechas con el mismo símbolo. Que no falte ninguna lo revisa check_dfa.

La función de transición extendida y el lenguaje de un DFA

La definición dice qué es un DFA. Falta decir qué hace con una cadena. La función δ\delta avanza un símbolo. Para avanzar una cadena entera se la aplica una vez por símbolo, y eso es una definición recursiva como las de la sección de inducción.

Definición. La función de transición extendida (extended transition function) de MM es δ∗:Q×Σ∗→Q\delta^* : Q \times \Sigma^* \to Q, definida así:

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

δ∗(q,w)\delta^*(q, w) es el estado en el que queda la máquina si empieza en qq y lee ww completa. La primera línea dice que sin leer nada no se mueve. La segunda, que para leer xaxa primero lee xx y después da un paso con aa.

Con el autómata de la paridad y w=110w = \mathtt{110}, la definición se desenrolla así:

δ∗(par,110)=δ(δ∗(par,11),0)=δ(δ(δ∗(par,1),1),0)=δ(δ(δ(δ∗(par,ε),1),1),0)=δ(δ(δ(par,1),1),0)=δ(δ(impar,1),0)=δ(par,0)=par\begin{aligned} \delta^*(\mathit{par}, \mathtt{110}) &= \delta(\delta^*(\mathit{par}, \mathtt{11}), \mathtt{0}) \\ &= \delta(\delta(\delta^*(\mathit{par}, \mathtt{1}), \mathtt{1}), \mathtt{0}) \\ &= \delta(\delta(\delta(\delta^*(\mathit{par}, \varepsilon), \mathtt{1}), \mathtt{1}), \mathtt{0}) \\ &= \delta(\delta(\delta(\mathit{par}, \mathtt{1}), \mathtt{1}), \mathtt{0}) \\ &= \delta(\delta(\mathit{impar}, \mathtt{1}), \mathtt{0}) \\ &= \delta(\mathit{par}, \mathtt{0}) \\ &= \mathit{par} \end{aligned}

Los estados que aparecen al resolver de adentro hacia afuera, par\mathit{par}, impar\mathit{impar}, par\mathit{par}, par\mathit{par}, son los mismos que run_dfa imprime de izquierda a derecha. Esa secuencia de estados se llama la ejecución de MM con ww. Si w=w1w2⋯wnw = w_1w_2 \cdots w_n, es la secuencia r0,r1,…,rnr_0, r_1, \ldots, r_n con r0=q0r_0 = q_0 y ri=δ(ri−1,wi)r_i = \delta(r_{i-1}, w_i). Tiene n+1n + 1 estados, uno más que los símbolos de ww, y su último estado es δ∗(q0,w)\delta^*(q_0, w). Sipser define la aceptación con esta secuencia, y es lo mismo dicho de otro modo.

Definición. MM acepta la cadena ww si δ∗(q0,w)∈F\delta^*(q_0, w) \in F. Si no, la rechaza. El lenguaje de MM es el conjunto de las cadenas que acepta:

L(M)={ w∈Σ∗:δ∗(q0,w)∈F }L(M) = \{\, w \in \Sigma^* : \delta^*(q_0, w) \in F \,\}

Se dice que MM reconoce el lenguaje L(M)L(M).

Tres precisiones sobre estas palabras, que se usan con cuidado todo el semestre.

  • Una máquina acepta cadenas y reconoce un lenguaje. Reconoce uno solo: L(M)L(M). Si MM no acepta ninguna cadena, igual reconoce un lenguaje, que es ∅\emptyset.
  • ”MM reconoce AA” quiere decir L(M)=AL(M) = A, con igualdad. MM tiene que aceptar todas las cadenas de AA y ninguna otra. Un autómata con F=QF = Q acepta todas las cadenas de cualquier lenguaje, y no por eso los reconoce: reconoce Σ∗\Sigma^*.
  • Solo cuenta el estado final. Que la ejecución pase por un estado de aceptación a mitad de camino no significa nada.

Error común. Decir que MM acepta ww porque “pasa por” un estado de aceptación. Con el autómata de la paridad, la ejecución de 1101\mathtt{1101} es par\mathit{par}, impar\mathit{impar}, par\mathit{par}, par\mathit{par}, impar\mathit{impar}: visita par tres veces y termina en impar. La rechaza.

Una propiedad de δ∗\delta^* que se usa todo el tiempo, casi sin nombrarla: leer uvuv es leer uu y, desde donde se quedó, leer vv.

Lema (de la concatenación). Para todo estado qq y todas las cadenas uu, vv: δ∗(q,uv)=δ∗(δ∗(q,u),v)\delta^*(q, uv) = \delta^*(\delta^*(q, u), v).

Demostración. Por inducción sobre la longitud de vv, con qq y uu fijos.

Caso base: v=εv = \varepsilon. Entonces δ∗(q,uε)=δ∗(q,u)\delta^*(q, u\varepsilon) = \delta^*(q, u), y por la primera línea de la definición δ∗(δ∗(q,u),ε)=δ∗(q,u)\delta^*(\delta^*(q, u), \varepsilon) = \delta^*(q, u). Son iguales.

Paso inductivo: v=xav = xa, y suponemos que el lema vale para xx. Entonces:

δ∗(q,u(xa))=δ∗(q,(ux)a)la concatenacioˊn es asociativa=δ(δ∗(q,ux),a)definicioˊn de δ∗=δ(δ∗(δ∗(q,u),x),a)hipoˊtesis de induccioˊn=δ∗(δ∗(q,u),xa)definicioˊn de δ∗, leıˊda de derecha a izquierda\begin{aligned} \delta^*(q, u(xa)) &= \delta^*(q, (ux)a) && \text{la concatenación es asociativa} \\ &= \delta(\delta^*(q, ux), a) && \text{definición de } \delta^* \\ &= \delta(\delta^*(\delta^*(q, u), x), a) && \text{hipótesis de inducción} \\ &= \delta^*(\delta^*(q, u), xa) && \text{definición de } \delta^* \text{, leída de derecha a izquierda} \end{aligned}

∎

El lema dice algo fuerte sobre lo que la máquina puede saber. Si dos cadenas uu y u′u' llevan al mismo estado, entonces uvuv y u′vu'v también, para cualquier continuación vv. Después de leer uu, la máquina no distingue si leyó uu o u′u': el estado es todo lo que recuerda.

En C++. Así queda δ∗\delta^* en dfa.h. El ciclo aplica la segunda línea de la definición una vez por símbolo. Con la cadena vacía no da ninguna vuelta y devuelve qq: la primera línea.

inline std::string delta_star(const Dfa& m, std::string q, const std::string& w) {
    for (char a : w) {
        q = step(m, q, a);
    }
    return q;
}

inline bool accepts(const Dfa& m, const std::string& w) {
    return m.accept.count(delta_star(m, m.start, w)) > 0;
}

Simular un DFA cuesta un paso por símbolo, y la memoria que usa no depende de la longitud de ww: una variable con el estado actual. Ningún otro modelo del curso va a ser tan barato.

Cómo diseñar un DFA

Diseñar un autómata es programar con una restricción extraña: no hay variables. Lo único que el programa puede recordar es en qué línea está. El método que sigue convierte esa restricción en una pregunta.

  1. Pónganse en el lugar de la máquina. Los símbolos llegan de uno en uno. No saben cuántos faltan, y después de cada uno les pueden decir “ahí terminó: ¿la cadena está en el lenguaje?”. Tienen que poder responder siempre.
  2. Decidan qué hay que recordar. ¿Qué necesitan saber de lo ya leído para responder ahora y para seguir respondiendo después de cualquier continuación? Tiene que ser una lista finita de posibilidades.
  3. Un estado por posibilidad. Cada estado es un hecho sobre lo leído hasta el momento: “la cantidad de unos es par”, “termina en 0”. Escriban ese hecho junto al estado. Es la documentación del autómata y será su demostración.
  4. Las transiciones salen solas. Para cada estado y cada símbolo: si el hecho del estado es cierto y llega este símbolo, ¿qué hecho pasa a ser cierto? Llenen la tabla completa, casilla por casilla.
  5. Inicial y aceptación. El estado inicial es el hecho que cumple la cadena vacía. Los de aceptación son los hechos que implican que la cadena está en el lenguaje.
  6. Prueben con cadenas cortas, empezando por ε\varepsilon y por las de longitud 1, antes de demostrar nada.

Los tres diseños que siguen están en machines/, y los usaremos el resto del capítulo.

Termina en 01

Lenguaje. A={ w∈{0,1}∗:w termina en 01 }A = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : w \text{ termina en } \mathtt{01} \,\}.

Qué recordar. Para saber si la cadena termina en 01\mathtt{01} basta conocer sus dos últimos símbolos. Eso da un autómata correcto con 7 estados: uno por cada cadena de longitud menor que 2, que son ε\varepsilon, 0\mathtt{0} y 1\mathtt{1}, y uno por cada par de últimos símbolos, 00\mathtt{00}, 01\mathtt{01}, 10\mathtt{10} y 11\mathtt{11}. Pero se recuerda de más. Lo que importa de lo leído es cuánto avance hay hacia un 01\mathtt{01} final:

Estado Lo que dice de lo leído hasta ahora
q0q_0 No termina en 0\mathtt{0} ni en 01\mathtt{01}: no hay nada aprovechable
q1q_1 Termina en 0\mathtt{0}: si ahora llega un 1\mathtt{1}, termina en 01\mathtt{01}
q2q_2 Termina en 01\mathtt{01}

Las tres posibilidades se excluyen entre sí y cubren todas las cadenas, porque una cadena que termina en 01\mathtt{01} termina en 1\mathtt{1} y no en 0\mathtt{0}.

Las transiciones. Si llega un 0\mathtt{0}, la cadena pasa a terminar en 0\mathtt{0}, venga de donde venga: la columna del 0\mathtt{0} es toda q1q_1. Si llega un 1\mathtt{1}, termina en 01\mathtt{01} solo si antes terminaba en 0\mathtt{0}, es decir, solo desde q1q_1. Desde q0q_0 o desde q2q_2, con un 1\mathtt{1} la cadena termina en 11\mathtt{11} o es la cadena 1\mathtt{1}, y no hay nada aprovechable: q0q_0.

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

     δ   0   1
->   q0  q1  q0
     q1  q1  q2
   * q2  q1  q0

estados alcanzables desde q0: 3 de 3

El estado inicial es q0q_0, porque ε\varepsilon no termina en 0\mathtt{0} ni en 01\mathtt{01}. El de aceptación es q2q_2.

$ build/run_dfa machines/ends_01.dfa 110101 010
w = 110101
  q0 -1-> q0 -1-> q0 -0-> q1 -1-> q2 -0-> q1 -1-> q2
  termina en q2, que está en F: acepta
w = 010
  q0 -0-> q1 -1-> q2 -0-> q1
  termina en q1, que no está en F: rechaza

En la primera ejecución la máquina llega a q2q_2 después de leer 1101\mathtt{1101}, sale, y vuelve a entrar. De q2q_2 hay que poder salir: que lo leído termine en 01\mathtt{01} es cierto ahora y deja de serlo con el símbolo siguiente.

Contiene 101

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

Qué recordar. Aquí hay un hecho que, una vez cierto, no deja de serlo: si 101\mathtt{101} ya apareció, la cadena está en BB termine como termine. Mientras no haya aparecido, importa cuánto de un 101\mathtt{101} está armado al final de lo leído.

Estado Lo que dice de lo leído hasta ahora
q0q_0 No contiene 101\mathtt{101}, y no termina en 1\mathtt{1} ni en 10\mathtt{10}
q1q_1 No contiene 101\mathtt{101}, y termina en 1\mathtt{1}
q2q_2 No contiene 101\mathtt{101}, y termina en 10\mathtt{10}
q3q_3 Contiene 101\mathtt{101}

Las transiciones. Las que avanzan son fáciles: q0q_0 con 1\mathtt{1} va a q1q_1, q1q_1 con 0\mathtt{0} va a q2q_2, y q2q_2 con 1\mathtt{1} va a q3q_3. Las difíciles son las que no avanzan, porque hay que decidir cuánto se conserva.

  • q1q_1 con 1\mathtt{1}: lo leído termina en 11\mathtt{11}. No avanzó, pero el último 1\mathtt{1} puede ser el inicio de un 101\mathtt{101}. Se queda en q1q_1.
  • q2q_2 con 0\mathtt{0}: lo leído termina en 100\mathtt{100}. Ningún final de 100\mathtt{100} sirve como inicio de 101\mathtt{101}. Vuelve a q0q_0.
  • q0q_0 con 0\mathtt{0}: sigue sin terminar en 1\mathtt{1} ni en 10\mathtt{10}. Se queda en q0q_0.
  • q3q_3 con cualquier símbolo: sigue conteniendo 101\mathtt{101}. Se queda en q3q_3.
$ build/show_dfa machines/contains_101.dfa
Q  = {q0, q1, q2, q3}
Σ  = {0, 1}
q0 = q0
F  = {q3}

     δ   0   1
->   q0  q0  q1
     q1  q2  q1
     q2  q0  q3
   * q3  q3  q3

estados alcanzables desde q0: 4 de 4
Diagrama de estados con cuatro estados en fila: q₀, q₁, q₂ y q₃. La flecha de inicio entra a q₀, y q₃ tiene doble círculo. Las flechas que avanzan son q₀ con 1 a q₁, q₁ con 0 a q₂, y q₂ con 1 a q₃. Las que no avanzan: q₀ tiene un bucle con 0, q₁ tiene un bucle con 1, y de q₂ sale una flecha curva con 0 que vuelve a q₀. q₃ tiene un bucle con 0 y con 1. Debajo de cada estado, lo que recuerda, con las letras de 101 que ya están armadas: en q₀ ninguna, lo leído no contiene 101 y no termina en 1 ni en 10; en q₁ la primera, no contiene 101 y termina en 1; en q₂ las dos primeras, no contiene 101 y termina en 10; en q₃ las tres, contiene 101 y ya no se saleDiagrama de estados con cuatro estados en fila: q₀, q₁, q₂ y q₃. La flecha de inicio entra a q₀, y q₃ tiene doble círculo. Las flechas que avanzan son q₀ con 1 a q₁, q₁ con 0 a q₂, y q₂ con 1 a q₃. Las que no avanzan: q₀ tiene un bucle con 0, q₁ tiene un bucle con 1, y de q₂ sale una flecha curva con 0 que vuelve a q₀. q₃ tiene un bucle con 0 y con 1. Debajo de cada estado, lo que recuerda, con las letras de 101 que ya están armadas: en q₀ ninguna, lo leído no contiene 101 y no termina en 1 ni en 10; en q₁ la primera, no contiene 101 y termina en 1; en q₂ las dos primeras, no contiene 101 y termina en 10; en q₃ las tres, contiene 101 y ya no se sale
Cada estado dice cuánto de 101 está armado al final de lo leído. Al fallar no siempre se vuelve al principio: desde q₁, un 1 conserva el avance.
$ build/run_dfa machines/contains_101.dfa 1100101 11011 110011
w = 1100101
  q0 -1-> q1 -1-> q1 -0-> q2 -0-> q0 -1-> q1 -0-> q2 -1-> q3
  termina en q3, que está en F: acepta
w = 11011
  q0 -1-> q1 -1-> q1 -0-> q2 -1-> q3 -1-> q3
  termina en q3, que está en F: acepta
w = 110011
  q0 -1-> q1 -1-> q1 -0-> q2 -0-> q0 -1-> q1 -1-> q1
  termina en q1, que no está en F: rechaza

Error común. Mandar q1q_1 con 1\mathtt{1} de vuelta a q0q_0, con la idea de que “se rompió el patrón y hay que empezar de nuevo”. Con ese cambio la cadena 11011\mathtt{11011} se rechaza: después de 11\mathtt{11} la máquina estaría en q0q_0, el 0\mathtt{0} la dejaría en q0q_0, y ya no alcanzaría a ver el 101\mathtt{101} del final. Cuando un intento falla, parte de lo leído puede servir para el intento siguiente.

El estado q3q_3 es un estado del que no se sale: todas sus flechas vuelven a él. Aquí es de aceptación, y significa “ya ganó”. En la sección El estado trampa aparece su gemelo, el que significa “ya perdió”.

Múltiplos de 3 en binario

Lenguaje.

C={ w∈{0,1}∗:w, leıˊda como nuˊmero en base 2, es un muˊltiplo de 3 }.C = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : w \text{, leída como número en base 2, es un múltiplo de 3} \,\}.

Hay que fijar la representación, como se dijo en De problemas a lenguajes. El número se lee con el bit más significativo primero, se permiten ceros a la izquierda, y la cadena vacía representa el 0. Llamemos val(w)\mathrm{val}(w) al número que representa ww: val(110)=6\mathrm{val}(\mathtt{110}) = 6, val(0011)=3\mathrm{val}(\mathtt{0011}) = 3, val(ε)=0\mathrm{val}(\varepsilon) = 0.

Qué recordar. El número no se puede recordar: crece sin tope y los estados son finitos. Pero no hace falta el número, sino su resto al dividirlo entre 3, que solo puede ser 0, 1 o 2. La pregunta es si el resto se puede mantener al día leyendo un bit más, y la respuesta viene de cómo funciona la base 2. Agregar un bit bb a la derecha de un número lo duplica y le suma bb:

val(wb)=2⋅val(w)+b\mathrm{val}(wb) = 2 \cdot \mathrm{val}(w) + b

Por ejemplo, val(110)=6\mathrm{val}(\mathtt{110}) = 6 y val(1101)=2⋅6+1=13\mathrm{val}(\mathtt{1101}) = 2 \cdot 6 + 1 = 13. Entonces el resto nuevo depende solo del resto viejo y del bit: si val(w)\mathrm{val}(w) deja resto rr, val(wb)\mathrm{val}(wb) deja el resto de 2r+b2r + b.

Estado Lo que dice Con 0\mathtt{0}: resto de 2r2r Con 1\mathtt{1}: resto de 2r+12r + 1
r0r_0 val\mathrm{val} deja resto 0 0→r00 \to r_0 1→r11 \to r_1
r1r_1 val\mathrm{val} deja resto 1 2→r22 \to r_2 3, resto 0→r00 \to r_0
r2r_2 val\mathrm{val} deja resto 2 4, resto 1→r11 \to r_1 5, resto 2→r22 \to r_2

El estado inicial es r0r_0, porque val(ε)=0\mathrm{val}(\varepsilon) = 0, y el de aceptación también es r0r_0.

$ build/run_dfa machines/multiple_of_3.dfa 10101 1101 0011
w = 10101
  r0 -1-> r1 -0-> r2 -1-> r2 -0-> r1 -1-> r0
  termina en r0, que está en F: acepta
w = 1101
  r0 -1-> r1 -1-> r0 -0-> r0 -1-> r1
  termina en r1, que no está en F: rechaza
w = 0011
  r0 -0-> r0 -0-> r0 -1-> r1 -1-> r0
  termina en r0, que está en F: acepta

10101\mathtt{10101} es 21=3⋅721 = 3 \cdot 7. 1101\mathtt{1101} es 13, que deja resto 1, y la máquina termina en r1r_1. Los prefijos de 10101\mathtt{10101} valen 1, 2, 5, 10 y 21, con restos 1, 2, 2, 1 y 0: los estados de la ejecución, uno por uno.

Idea clave. Diseñar un DFA es decidir qué recordar. Cada estado es un hecho sobre lo leído hasta ahora, los hechos se excluyen entre sí y cubren todos los casos, y cada transición dice cómo cambia el hecho al llegar un símbolo. Si lo que hay que recordar no cabe en una lista finita, no hay DFA.

En la práctica. El autómata de Contiene 101 es un buscador de texto: lee una sola vez, nunca retrocede en la entrada, y avisa cuando apareció el patrón. Las herramientas que buscan patrones en archivos muy grandes trabajan con autómatas así, construidos por un programa a partir del patrón. En la semana 3 veremos esa construcción, y el laboratorio será un grep pequeño.

Demostrar que un DFA es correcto

Probar un autómata con muchas cadenas da confianza, y las pruebas de esta semana lo hacen con todas las cadenas de longitud hasta 12. Pero un lenguaje infinito no se termina de probar. Para afirmar L(M)=AL(M) = A hace falta una demostración, y hay un método que funciona casi siempre.

El método es demostrar más de lo que se pide. No solo que MM acepta las cadenas correctas, sino en qué estado queda con cada cadena. Se escribe una afirmación por estado, que es el hecho que se anotó al diseñar, y se demuestran todas juntas por inducción sobre la longitud de la cadena.

¿Por qué demostrar más es más fácil? Porque la hipótesis de inducción también dice más. Para saber qué pasa con xaxa hay que saber dónde quedó la máquina con xx, y ”xx está o no está en el lenguaje” no alcanza para saberlo.

La demostración para la paridad

Afirmación. Sea MM el autómata de machines/even_ones.dfa. Para toda cadena w∈{0,1}∗w \in \{\mathtt{0}, \mathtt{1}\}^*:

  • δ∗(par,w)=par\delta^*(\mathit{par}, w) = \mathit{par} si ww tiene una cantidad par de unos, y
  • δ∗(par,w)=impar\delta^*(\mathit{par}, w) = \mathit{impar} si ww tiene una cantidad impar de unos.

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

Caso base: w=εw = \varepsilon. Tiene cero unos, que es una cantidad par, y δ∗(par,ε)=par\delta^*(\mathit{par}, \varepsilon) = \mathit{par} por definición. Se cumple.

Paso inductivo: sea w=xaw = xa, y supongamos la afirmación para xx. Hay cuatro casos, según la paridad de los unos de xx y según aa.

  • xx tiene una cantidad par de unos y a=0a = \mathtt{0}. Por hipótesis δ∗(par,x)=par\delta^*(\mathit{par}, x) = \mathit{par}, así que δ∗(par,w)=δ(par,0)=par\delta^*(\mathit{par}, w) = \delta(\mathit{par}, \mathtt{0}) = \mathit{par}. Y ww tiene los mismos unos que xx: una cantidad par. Se cumple.
  • xx par y a=1a = \mathtt{1}. δ∗(par,w)=δ(par,1)=impar\delta^*(\mathit{par}, w) = \delta(\mathit{par}, \mathtt{1}) = \mathit{impar}, y ww tiene un uno más que xx: una cantidad impar. Se cumple.
  • xx impar y a=0a = \mathtt{0}. δ∗(par,w)=δ(impar,0)=impar\delta^*(\mathit{par}, w) = \delta(\mathit{impar}, \mathtt{0}) = \mathit{impar}, y ww tiene los mismos unos que xx. Se cumple.
  • xx impar y a=1a = \mathtt{1}. δ∗(par,w)=δ(impar,1)=par\delta^*(\mathit{par}, w) = \delta(\mathit{impar}, \mathtt{1}) = \mathit{par}, y ww tiene un uno más: una cantidad par. Se cumple.

∎

Cada caso del paso inductivo es una casilla de la tabla de transiciones. La demostración recorre la tabla y comprueba, casilla por casilla, que el hecho del estado de llegada es cierto.

Corolario. L(M)L(M) es el lenguaje de las cadenas con una cantidad par de unos. En efecto, MM acepta ww si y solo si δ∗(par,w)∈F={par}\delta^*(\mathit{par}, w) \in F = \{\mathit{par}\}, y por la afirmación eso pasa si y solo si ww tiene una cantidad par de unos. Las dos direcciones salen de la misma afirmación: si ww tiene cantidad par, termina en par\mathit{par} y se acepta; si tiene cantidad impar, termina en impar\mathit{impar} y se rechaza.

La demostración para Termina en 01

Afirmación. Sea MM el autómata de machines/ends_01.dfa. Para toda cadena w∈{0,1}∗w \in \{\mathtt{0}, \mathtt{1}\}^*:

  • (a) si ww termina en 01\mathtt{01}, entonces δ∗(q0,w)=q2\delta^*(q_0, w) = q_2;
  • (b) si ww termina en 0\mathtt{0}, entonces δ∗(q0,w)=q1\delta^*(q_0, w) = q_1;
  • (c) si ww no termina en 0\mathtt{0} ni en 01\mathtt{01}, entonces δ∗(q0,w)=q0\delta^*(q_0, w) = q_0.

Toda cadena cumple exactamente una de las tres condiciones, así que la afirmación dice en qué estado queda MM con cada cadena.

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

Caso base: w=εw = \varepsilon. No termina en 0\mathtt{0} ni en 01\mathtt{01}, así que le toca (c), y δ∗(q0,ε)=q0\delta^*(q_0, \varepsilon) = q_0. Se cumple.

Paso inductivo: sea w=xaw = xa, y supongamos la afirmación para xx. Llamemos p=δ∗(q0,x)p = \delta^*(q_0, x), de modo que δ∗(q0,w)=δ(p,a)\delta^*(q_0, w) = \delta(p, a).

  • a=0a = \mathtt{0}. Entonces ww termina en 0\mathtt{0}, y le toca (b): hay que ver que δ(p,0)=q1\delta(p, \mathtt{0}) = q_1. La columna del 0\mathtt{0} de la tabla es q1q_1 en las tres filas, así que se cumple sea cual sea pp. Aquí ni siquiera se usa la hipótesis.
  • a=1a = \mathtt{1} y xx termina en 0\mathtt{0}. Entonces ww termina en 01\mathtt{01}, y le toca (a). Por la hipótesis (b) aplicada a xx, p=q1p = q_1. Y δ(q1,1)=q2\delta(q_1, \mathtt{1}) = q_2. Se cumple.
  • a=1a = \mathtt{1} y xx no termina en 0\mathtt{0}. Entonces ww termina en 1\mathtt{1} y su penúltimo símbolo, si existe, no es 0\mathtt{0}: ww no termina en 0\mathtt{0} ni en 01\mathtt{01}, y le toca (c). Como xx no termina en 0\mathtt{0}, por la hipótesis le tocó (a) o (c), así que pp es q2q_2 o q0q_0. En la tabla, δ(q2,1)=q0\delta(q_2, \mathtt{1}) = q_0 y δ(q0,1)=q0\delta(q_0, \mathtt{1}) = q_0. Se cumple.

∎

Corolario. L(M)=AL(M) = A, el lenguaje de las cadenas que terminan en 01\mathtt{01}. Si ww termina en 01\mathtt{01}, por (a) queda en q2∈Fq_2 \in F y MM la acepta. Si no termina en 01\mathtt{01}, le toca (b) o (c), queda en q1q_1 o en q0q_0, que no están en FF, y MM la rechaza.

Para los otros dos diseños el esquema es idéntico, y quedan como ejercicios. Las afirmaciones son las de sus tablas de estados. En Múltiplos de 3 se reduce a una línea: δ∗(r0,w)=rk\delta^*(r_0, w) = r_k, donde kk es el resto de val(w)\mathrm{val}(w) entre 3, y el paso inductivo es la cuenta val(xb)=2⋅val(x)+b\mathrm{val}(xb) = 2 \cdot \mathrm{val}(x) + b junto con las seis casillas de la tabla.

Idea clave. Para demostrar que un DFA reconoce un lenguaje se escribe una afirmación por estado, ”MM queda en qq exactamente con las cadenas que cumplen tal cosa”, y se demuestran todas a la vez por inducción sobre la longitud. El caso base es la cadena vacía y el estado inicial. El paso inductivo es la tabla de transiciones, casilla por casilla.

Error común. Demostrar una sola dirección. “Toda cadena que termina en 01\mathtt{01} es aceptada” no basta: un autómata que acepta todo también lo cumple. Hay que mostrar además que las demás cadenas se rechazan. Con una afirmación por estado, las dos direcciones salen juntas.

Las pruebas de la semana comprueban estas afirmaciones por fuerza bruta: test_dfa recorre todas las cadenas binarias de longitud a lo sumo 12, que son 213−1=81912^{13} - 1 = 8191, y verifica con cada una que el autómata queda en el estado que su afirmación dice. No reemplaza la demostración, pero encuentra en segundos una casilla mal llenada.

El estado trampa

Lenguaje. E={ w∈{0,1}∗:w empieza con 1 }E = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : w \text{ empieza con } \mathtt{1} \,\}.

El primer intento suele tener dos estados: q0q_0, “todavía no leí nada”, y q1q_1, “empezó con 1\mathtt{1}”, que es de aceptación y del que no se sale. La flecha de q0q_0 a q1q_1 lleva un 1\mathtt{1}. ¿Y q0q_0 con 0\mathtt{0}? Si la cadena empieza con 0\mathtt{0} ya no está en EE, así que es tentador no dibujar nada: “ahí la máquina se muere”.

Eso no es un DFA. En un DFA, δ\delta es una función definida para todos los pares, y el archivo errors/missing_trap.dfa, que describe ese intento, no se puede cargar:

$ build/show_dfa errors/missing_trap.dfa
error: errors/missing_trap.dfa: falta la transición δ(q0, 0): en un DFA, δ es total

La solución es darle un lugar a “ya perdió”: un estado que no es de aceptación y del que no se sale. Se llama estado trampa.

$ build/show_dfa machines/starts_with_1.dfa
Q  = {q0, q1, trampa}
Σ  = {0, 1}
q0 = q0
F  = {q1}

     δ       0       1
->   q0      trampa  q1
   * q1      q1      q1
     trampa  trampa  trampa

estados alcanzables desde q0: 3 de 3

El estado trampa también es un hecho sobre lo leído, como cualquier otro: “la cadena empezó con 0\mathtt{0}”. Y como cualquier otro, cuenta en el número de estados.

Error común. Olvidar el estado trampa y dejar transiciones sin definir. En un DFA, δ\delta es total: de cada estado sale exactamente una flecha por cada símbolo. Muchos libros y muchas pizarras omiten el estado trampa en los dibujos para que queden limpios, con el acuerdo de que una flecha que falta va a él. En este curso se escribe siempre. El formato .dfa lo exige, y más abajo veremos una construcción, la del complemento, que da una respuesta equivocada si falta.

Hay un segundo error que el formato detecta: dos transiciones para el mismo estado y el mismo símbolo.

$ build/show_dfa errors/two_transitions.dfa
error: errors/two_transitions.dfa: línea 9: transición repetida para δ(q0, 0): en un DFA hay una sola

Una máquina que puede elegir entre dos flechas no es determinista. No es un disparate: es el modelo de la semana próxima, el NFA. Pero no es un DFA.

Lenguajes regulares

Ya hay varios lenguajes para los que construimos un DFA. Tienen nombre.

Definición. Un lenguaje es regular (regular language) si algún DFA lo reconoce.

Los lenguajes AA, BB, CC y EE de las secciones anteriores son regulares, y también el de la paridad. Para demostrar que un lenguaje es regular basta con mostrar un DFA y demostrar que lo reconoce. Para demostrar que no lo es hay que probar que ningún DFA sirve, de ningún tamaño, y eso pide herramientas que llegan en la semana 4.

Los lenguajes regulares son la primera clase de lenguajes del curso, la más pequeña. Las preguntas que nos haremos sobre cada clase son siempre las mismas: qué máquinas la definen, qué lenguajes quedan fuera, y si la clase es cerrada bajo las operaciones de lenguajes. Es decir: si AA y BB están en la clase, ¿también están A∪BA \cup B, A∩BA \cap B, el complemento de AA? El resto del capítulo responde eso para tres operaciones.

La construcción del producto

Problema. Tenemos un DFA M1M_1 que reconoce las cadenas con una cantidad par de unos, y un DFA M2M_2 que reconoce las que terminan en 01\mathtt{01}. Queremos un DFA para las cadenas que cumplen las dos condiciones.

Un programa normal correría M1M_1 con la cadena, luego M2M_2 con la misma cadena, y juntaría las respuestas. Un DFA no puede: lee la entrada una sola vez. Tiene que correr las dos máquinas a la vez, símbolo por símbolo. Para eso necesita recordar en qué estado va cada una, y eso es un par de estados. Hay una cantidad finita de pares, así que cada par puede ser un estado de la máquina nueva.

Construcción. Sean M1=(Q1,Σ,δ1,q1,F1)M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1) y M2=(Q2,Σ,δ2,q2,F2)M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2) dos DFA con el mismo alfabeto. El producto de M1M_1 y M2M_2 es el DFA M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) con:

  • Q=Q1×Q2Q = Q_1 \times Q_2, los pares (p,q)(p, q) con p∈Q1p \in Q_1 y q∈Q2q \in Q_2.
  • δ((p,q),a)=(δ1(p,a),δ2(q,a))\delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a)): cada componente avanza con su propia función.
  • q0=(q1,q2)q_0 = (q_1, q_2), los dos estados iniciales.
  • FF depende de lo que se quiera:
    • para la intersección, F=F1×F2F = F_1 \times F_2: los pares donde los dos aceptan;
    • para la unión, F={ (p,q):p∈F1 o q∈F2 }F = \{\, (p, q) : p \in F_1 \text{ o } q \in F_2 \,\}: los pares donde alguno acepta.

Es un DFA: QQ es finito, con ∣Q1∣⋅∣Q2∣|Q_1| \cdot |Q_2| estados, y δ\delta está definida para todos los pares y todos los símbolos, porque δ1\delta_1 y δ2\delta_2 lo están.

Con los dos autómatas del problema, el producto tiene 2×3=62 \times 3 = 6 estados. Conviene pensarlos como una cuadrícula, con una fila por estado de M1M_1 y una columna por estado de M2M_2:

Los seis estados del producto en una cuadrícula de dos filas, par e impar, que son los estados de M₁, y tres columnas, q₀, q₁ y q₂, que son los de M₂. El estado inicial es (par, q₀). Las flechas con 0 se quedan en su fila y van siempre a la columna q₁: en la fila par, de (par, q₀) a (par, q₁), un bucle en (par, q₁), y de (par, q₂) a (par, q₁); en la fila impar, lo mismo. Las flechas con 1 cambian siempre de fila: (par, q₀) e (impar, q₀) se apuntan una a la otra; de (par, q₁) a (impar, q₂); de (impar, q₁) a (par, q₂); de (par, q₂) a (impar, q₀); de (impar, q₂) a (par, q₀). Dos franjas marcan dónde acepta cada máquina: la fila par, donde acepta M₁, y la columna q₂, donde acepta M₂. La leyenda dice que para la intersección F es el cruce, (par, q₂), y que para la unión F son las dos franjas, 4 estadosLos seis estados del producto en una cuadrícula de dos filas, par e impar, que son los estados de M₁, y tres columnas, q₀, q₁ y q₂, que son los de M₂. El estado inicial es (par, q₀). Las flechas con 0 se quedan en su fila y van siempre a la columna q₁: en la fila par, de (par, q₀) a (par, q₁), un bucle en (par, q₁), y de (par, q₂) a (par, q₁); en la fila impar, lo mismo. Las flechas con 1 cambian siempre de fila: (par, q₀) e (impar, q₀) se apuntan una a la otra; de (par, q₁) a (impar, q₂); de (impar, q₁) a (par, q₂); de (par, q₂) a (impar, q₀); de (impar, q₂) a (par, q₀). Dos franjas marcan dónde acepta cada máquina: la fila par, donde acepta M₁, y la columna q₂, donde acepta M₂. La leyenda dice que para la intersección F es el cruce, (par, q₂), y que para la unión F son las dos franjas, 4 estados
El producto de los dos autómatas, con sus 12 transiciones. La fila dice en qué estado va M₁ y la columna, en cuál va M₂.

Un 0\mathtt{0} no cambia la paridad, así que con 0\mathtt{0} la máquina se mueve dentro de su fila. Un 1\mathtt{1} la cambia siempre de fila. La columna se mueve como en M2M_2. El programa product aplica la construcción a dos archivos y escribe el resultado en el mismo formato:

$ build/product inter machines/even_ones.dfa machines/ends_01.dfa
# Producto de machines/even_ones.dfa y machines/ends_01.dfa: intersección.
# 2 × 3 = 6 estados.
states: (par,q0) (par,q1) (par,q2) (impar,q0) (impar,q1) (impar,q2)
alphabet: 0 1
start: (par,q0)
accept: (par,q2)
delta:
(par,q0) 0 (par,q1)
(par,q0) 1 (impar,q0)
(par,q1) 0 (par,q1)
(par,q1) 1 (impar,q2)
(par,q2) 0 (par,q1)
(par,q2) 1 (impar,q0)
(impar,q0) 0 (impar,q1)
(impar,q0) 1 (par,q0)
(impar,q1) 0 (impar,q1)
(impar,q1) 1 (par,q2)
(impar,q2) 0 (impar,q1)
(impar,q2) 1 (par,q0)

El único estado de aceptación es (par,q2)(\mathit{par}, q_2): cantidad par de unos y termina en 01\mathtt{01}. Como la salida es un archivo .dfa, se le puede pasar a run_dfa, que lee de la entrada estándar si en lugar del archivo se le da -:

$ build/product inter machines/even_ones.dfa machines/ends_01.dfa | build/run_dfa - 1101 1001
w = 1101
  (par,q0) -1-> (impar,q0) -1-> (par,q0) -0-> (par,q1) -1-> (impar,q2)
  termina en (impar,q2), que no está en F: rechaza
w = 1001
  (par,q0) -1-> (impar,q0) -0-> (impar,q1) -0-> (impar,q1) -1-> (par,q2)
  termina en (par,q2), que está en F: acepta

La ejecución con 1101\mathtt{1101}, al lado de las dos ejecuciones por separado:

Leído M1M_1 M2M_2 El producto
ε\varepsilon par\mathit{par} q0q_0 (par,q0)(\mathit{par}, q_0)
1\mathtt{1} impar\mathit{impar} q0q_0 (impar,q0)(\mathit{impar}, q_0)
11\mathtt{11} par\mathit{par} q0q_0 (par,q0)(\mathit{par}, q_0)
110\mathtt{110} par\mathit{par} q1q_1 (par,q1)(\mathit{par}, q_1)
1101\mathtt{1101} impar\mathit{impar} q2q_2 (impar,q2)(\mathit{impar}, q_2)

La columna del producto es, fila por fila, el par formado por las otras dos. Eso es lo que hay que demostrar. 1101\mathtt{1101} termina en 01\mathtt{01} pero tiene tres unos: M2M_2 la acepta, M1M_1 no, y el producto para la intersección la rechaza.

Animación de la construcción del producto con la cadena 1101. A la izquierda están los diagramas de M₁, el de la cantidad par de unos, y de M₂, el que termina en 01; a la derecha, la cuadrícula de los seis pares, con (par, q₂) como único estado de aceptación. En cada paso las dos máquinas leen el mismo símbolo, y en la cuadrícula se resaltan la fila del estado de M₁, la columna del estado de M₂ y el par donde se cruzan. Leído ε: M₁ en par, M₂ en q₀, el producto en (par, q₀). Leído 1: impar, q₀, (impar, q₀). Leído 11: par, q₀, (par, q₀). Leído 110: par, q₁, (par, q₁). Leído 1101: impar, q₂, (impar, q₂). Al final M₂ acepta y M₁ no: (impar, q₂) no está en F₁ × F₂, y el producto rechazaAnimación de la construcción del producto con la cadena 1101. A la izquierda están los diagramas de M₁, el de la cantidad par de unos, y de M₂, el que termina en 01; a la derecha, la cuadrícula de los seis pares, con (par, q₂) como único estado de aceptación. En cada paso las dos máquinas leen el mismo símbolo, y en la cuadrícula se resaltan la fila del estado de M₁, la columna del estado de M₂ y el par donde se cruzan. Leído ε: M₁ en par, M₂ en q₀, el producto en (par, q₀). Leído 1: impar, q₀, (impar, q₀). Leído 11: par, q₀, (par, q₀). Leído 110: par, q₁, (par, q₁). Leído 1101: impar, q₂, (impar, q₂). Al final M₂ acepta y M₁ no: (impar, q₂) no está en F₁ × F₂, y el producto rechaza
La tabla de arriba, en movimiento. El producto no hace nada nuevo: anota en un solo estado por dónde va cada una de las dos máquinas.

Por qué funciona

Lema (del producto). Para todo par (p,q)∈Q(p, q) \in Q y toda cadena ww: δ∗((p,q),w)=(δ1∗(p,w),δ2∗(q,w))\delta^*((p, q), w) = (\delta_1^*(p, w), \delta_2^*(q, w)).

Con palabras: correr el producto es lo mismo que correr las dos máquinas, cada una por su lado, y juntar los resultados.

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

Caso base: w=εw = \varepsilon. Por la definición de la función extendida, δ∗((p,q),ε)=(p,q)\delta^*((p, q), \varepsilon) = (p, q), y también δ1∗(p,ε)=p\delta_1^*(p, \varepsilon) = p y δ2∗(q,ε)=q\delta_2^*(q, \varepsilon) = q. Los dos lados son (p,q)(p, q).

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

δ∗((p,q),xa)=δ(δ∗((p,q),x),a)definicioˊn de δ∗=δ((δ1∗(p,x),δ2∗(q,x)),a)hipoˊtesis de induccioˊn=(δ1(δ1∗(p,x),a),δ2(δ2∗(q,x),a))definicioˊn de δ en el producto=(δ1∗(p,xa),δ2∗(q,xa))definicioˊn de δ1∗ y de δ2∗\begin{aligned} \delta^*((p, q), xa) &= \delta(\delta^*((p, q), x), a) && \text{definición de } \delta^* \\ &= \delta((\delta_1^*(p, x), \delta_2^*(q, x)), a) && \text{hipótesis de inducción} \\ &= (\delta_1(\delta_1^*(p, x), a), \delta_2(\delta_2^*(q, x), a)) && \text{definición de } \delta \text{ en el producto} \\ &= (\delta_1^*(p, xa), \delta_2^*(q, xa)) && \text{definición de } \delta_1^* \text{ y de } \delta_2^* \end{aligned}

∎

Teorema. Si A1A_1 y A2A_2 son lenguajes regulares sobre el mismo alfabeto, entonces A1∩A2A_1 \cap A_2 y A1∪A2A_1 \cup A_2 también son regulares.

Demostración. Por construcción. Como A1A_1 y A2A_2 son regulares, hay DFA M1M_1 y M2M_2 con L(M1)=A1L(M_1) = A_1 y L(M2)=A2L(M_2) = A_2.

Qué se construye: el producto MM de M1M_1 y M2M_2, con F=F1×F2F = F_1 \times F_2.

Por qué reconoce A1∩A2A_1 \cap A_2: para toda cadena ww,

M acepta w  ⟺  δ∗((q1,q2),w)∈F1×F2definicioˊn de aceptar  ⟺  (δ1∗(q1,w),δ2∗(q2,w))∈F1×F2lema del producto  ⟺  δ1∗(q1,w)∈F1 y δ2∗(q2,w)∈F2definicioˊn de F1×F2  ⟺  M1 acepta w y M2 acepta w  ⟺  w∈A1∩A2\begin{aligned} M \text{ acepta } w &\iff \delta^*((q_1, q_2), w) \in F_1 \times F_2 && \text{definición de aceptar} \\ &\iff (\delta_1^*(q_1, w), \delta_2^*(q_2, w)) \in F_1 \times F_2 && \text{lema del producto} \\ &\iff \delta_1^*(q_1, w) \in F_1 \text{ y } \delta_2^*(q_2, w) \in F_2 && \text{definición de } F_1 \times F_2 \\ &\iff M_1 \text{ acepta } w \text{ y } M_2 \text{ acepta } w \\ &\iff w \in A_1 \cap A_2 \end{aligned}

Cada línea es un “si y solo si”, así que la cadena de equivalencias demuestra las dos direcciones: toda cadena de A1∩A2A_1 \cap A_2 se acepta, y toda cadena aceptada está en A1∩A2A_1 \cap A_2. Luego L(M)=A1∩A2L(M) = A_1 \cap A_2.

Para la unión: se toma la misma máquina con F={ (p,q):p∈F1 o q∈F2 }F = \{\, (p, q) : p \in F_1 \text{ o } q \in F_2 \,\}. La cadena de equivalencias es la misma con “o” en lugar de “y” en las tres últimas líneas. ∎

Si los alfabetos no coinciden, primero se igualan: se usa Σ1∪Σ2\Sigma_1 \cup \Sigma_2 en las dos máquinas, y a cada una se le agrega un estado trampa al que van los símbolos que no conocía. Una cadena con un símbolo ajeno a Σ1\Sigma_1 no está en A1A_1, y la trampa dice exactamente eso.

La misma máquina con distinto F

Para la unión no hay que construir nada nuevo. Los estados, las transiciones y el estado inicial son los mismos, y solo cambia cuáles se marcan:

$ build/product union machines/even_ones.dfa machines/ends_01.dfa | head -6
# Producto de machines/even_ones.dfa y machines/ends_01.dfa: unión.
# 2 × 3 = 6 estados.
states: (par,q0) (par,q1) (par,q2) (impar,q0) (impar,q1) (impar,q2)
alphabet: 0 1
start: (par,q0)
accept: (par,q0) (par,q1) (par,q2) (impar,q2)

En la cuadrícula, la unión marca toda la fila par y toda la columna q2: cuatro estados. La intersección marcaba solo el cruce.

Error común. Usar F1×F2F_1 \times F_2 para la unión, o creer que el FF de la unión es F1∪F2F_1 \cup F_2. Lo segundo ni siquiera tiene el tipo correcto: F1∪F2F_1 \cup F_2 es un conjunto de estados sueltos, y los estados del producto son pares. Para la unión, un par es de aceptación si alguna de sus componentes lo es: (F1×Q2)∪(Q1×F2)(F_1 \times Q_2) \cup (Q_1 \times F_2).

Idea clave. El producto corre dos DFA a la vez: su estado es el par de estados de los dos. El conjunto FF elige qué se hace con las dos respuestas. Con una máquina de ∣Q1∣⋅∣Q2∣|Q_1| \cdot |Q_2| estados salen la unión, la intersección y cualquier otra combinación de ”M1M_1 acepta” y ”M2M_2 acepta”.

¿Todos los pares se alcanzan?

El producto de un autómata de 3 estados y uno de 4 tiene 12 estados. Que todos sirvan es otra cosa. Un estado es alcanzable si alguna cadena lleva hasta él desde el estado inicial. Los que no lo son están en la definición, pero ninguna ejecución pasa por ellos, y se pueden borrar sin cambiar el lenguaje.

En el ejemplo de la cuadrícula se alcanzan los 6. No siempre es así. El caso extremo es el producto de una máquina consigo misma:

$ build/product inter machines/even_ones.dfa machines/even_ones.dfa --alcanzables
# Producto de machines/even_ones.dfa y machines/even_ones.dfa: intersección.
# 2 × 2 = 4 estados, 2 alcanzables.
states: (par,par) (impar,impar)
alphabet: 0 1
start: (par,par)
accept: (par,par)
delta:
(par,par) 0 (par,par)
(par,par) 1 (impar,impar)
(impar,impar) 0 (impar,impar)
(impar,impar) 1 (par,par)

Las dos copias leen lo mismo y van siempre en el mismo estado: (par,impar)(\mathit{par}, \mathit{impar}) no puede pasar. Un caso menos artificial es el producto de Termina en 01 y Contiene 101, de 3×4=123 \times 4 = 12 estados. El programa informa 3 × 4 = 12 estados, 8 alcanzables, y deja estos:

(q0,q0) (q0,q1) (q0,q3) (q1,q0) (q1,q2) (q1,q3) (q2,q1) (q2,q3)

Los cuatro que faltan son pares de hechos que se contradicen. Por ejemplo (q1,q1)(q_1, q_1) diría que lo leído termina en 0\mathtt{0}, por el primer autómata, y termina en 1\mathtt{1}, por el segundo. Y (q2,q0)(q_2, q_0) diría que termina en 01\mathtt{01} y que no termina en 1\mathtt{1}.

En la práctica. Un programa que construye productos no genera los ∣Q1∣⋅∣Q2∣|Q_1| \cdot |Q_2| pares: parte del par inicial y agrega solo los que va encontrando al seguir las transiciones, como un recorrido de un grafo. Con dos máquinas no importa. Con el producto de diez máquinas de 10 estados, la diferencia es entre 101010^{10} pares posibles y los que de verdad aparecen. La misma idea vuelve la semana próxima, en la construcción de subconjuntos.

Complemento

Teorema. Si AA es un lenguaje regular sobre Σ\Sigma, su complemento Σ∗−A\Sigma^* - A también es regular.

Demostración. Por construcción. Sea M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) un DFA con L(M)=AL(M) = A.

Qué se construye: M′=(Q,Σ,δ,q0,Q−F)M' = (Q, \Sigma, \delta, q_0, Q - F). La misma máquina, con los estados de aceptación intercambiados: los que lo eran dejan de serlo, y los que no lo eran pasan a serlo.

Por qué reconoce el complemento: MM y M′M' tienen los mismos estados y la misma δ\delta, así que tienen la misma δ∗\delta^*. Para toda cadena w∈Σ∗w \in \Sigma^*, el estado δ∗(q0,w)\delta^*(q_0, w) existe y es uno solo, y está en FF o en Q−FQ - F, pero no en los dos. Entonces:

M′ acepta w  ⟺  δ∗(q0,w)∈Q−F  ⟺  δ∗(q0,w)∉F  ⟺  M no acepta w  ⟺  w∉AM' \text{ acepta } w \iff \delta^*(q_0, w) \in Q - F \iff \delta^*(q_0, w) \notin F \iff M \text{ no acepta } w \iff w \notin A

∎

$ build/complement machines/starts_with_1.dfa
# Complemento de machines/starts_with_1.dfa.
states: q0 q1 trampa
alphabet: 0 1
start: q0
accept: q0 trampa
delta:
q0 0 trampa
q0 1 q1
q1 0 q1
q1 1 q1
trampa 0 trampa
trampa 1 trampa

El complemento de “empieza con 1\mathtt{1}” son las cadenas que no empiezan con 1\mathtt{1}: la vacía, que queda en q0q_0, y las que empiezan con 0\mathtt{0}, que quedan en trampa. Los dos estados son ahora de aceptación.

La demostración usa, en una frase que es fácil pasar por alto, que δ∗(q0,w)\delta^*(q_0, w) existe para toda cadena. Eso vale porque δ\delta es total. Con el “autómata” de dos estados sin trampa, la cuenta sale mal: al intercambiar FF quedaría solo q0q_0 como estado de aceptación. La cadena 0\mathtt{0} no tiene por dónde seguir desde q0q_0, así que no se acepta ni antes ni después del intercambio. Pero 0\mathtt{0} no empieza con 1\mathtt{1}: debería estar en el complemento. El intercambio solo es correcto cuando toda cadena termina en algún estado.

Error común. Complementar un autómata al que le falta el estado trampa. Primero se completa δ\delta y después se intercambian los estados de aceptación. El mismo cuidado hará falta la semana próxima: en un NFA, intercambiar los estados de aceptación no da el complemento.

Con complemento e intersección, la unión sale también de las leyes de De Morgan: A∪BA \cup B es el complemento de la intersección de los complementos. Si se hace con máquinas, el resultado es el mismo producto con el mismo FF que da la construcción directa, y test_product lo comprueba.

Lo que un DFA no puede hacer

Todo lo construido esta semana recuerda una cantidad acotada de información: una paridad, un resto, los últimos símbolos. El lenguaje { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} de la sección Lenguajes pide otra cosa. Para saber si los unos son tantos como los ceros hay que recordar cuántos ceros hubo, y esa cantidad no tiene tope.

La intuición de por qué ningún DFA alcanza es esta. Supongan un DFA con nn estados, y denle a leer las cadenas ε,0,00,…,0n\varepsilon, \mathtt{0}, \mathtt{00}, \ldots, \mathtt{0}^n. Son n+1n + 1 cadenas y hay nn estados, así que dos de ellas, digamos 0i\mathtt{0}^i y 0j\mathtt{0}^j con i≠ji \neq j, lo dejan en el mismo estado. Por el lema de la concatenación, desde ahí la máquina hará lo mismo con cualquier continuación: 0i1i\mathtt{0}^i\mathtt{1}^i y 0j1i\mathtt{0}^j\mathtt{1}^i terminan en el mismo estado, y se aceptan las dos o se rechazan las dos. Pero la primera está en el lenguaje y la segunda no. Un DFA con nn estados no puede distinguir n+1n + 1 cantidades.

Esto es solo la idea. La demostración cuidadosa, y dos herramientas generales para demostrar que un lenguaje no es regular, son el tema de la semana 4. Antes, en las semanas 2 y 3, veremos que los lenguajes regulares son más robustos de lo que parece: darle a la máquina la capacidad de adivinar no agrega ningún lenguaje, y las expresiones regulares describen exactamente la misma clase.

El código de la semana

code/week-01/
├── languages.h           cadenas y lenguajes finitos: prefijos, concatenación, estrella
├── strings_demo.cpp      las primeras cadenas de Σ*, y los prefijos, sufijos y subcadenas
├── languages_demo.cpp    operaciones con lenguajes finitos; ∅ frente a {ε}
├── dfa.h                 struct Dfa, lectura del formato .dfa, δ*, producto y complemento
├── show_dfa.cpp          muestra un .dfa como quíntupla y como tabla
├── run_dfa.cpp           la ejecución de un DFA con una o más cadenas
├── product.cpp           construcción del producto de dos .dfa
├── complement.cpp        complemento de un .dfa
├── machines/             los autómatas del capítulo, en formato .dfa
├── errors/               tres descripciones que no son un DFA
├── test_languages.cpp    pruebas de la sesión A
├── test_dfa.cpp          cada autómata contra un predicado; una afirmación por estado
├── test_product.cpp      el producto reconoce la intersección y la unión; complemento
└── lab/dfa_sim/          el laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan. Las pruebas comprueban con assert lo que este capítulo afirma. test_languages revisa los conteos de cadenas, los ejemplos de prefijos y las operaciones con ∅\emptyset y {ε}\{\varepsilon\}. test_dfa compara cada autómata de machines/ con una función de C++ que decide el mismo lenguaje mirando la cadena completa, sobre las 8191 cadenas de longitud a lo sumo 12, y comprueba la afirmación de cada estado, las ejecuciones copiadas en estos apuntes y el lema de la concatenación. test_product comprueba el lema del producto desde todos los pares, que el producto reconoce la intersección y la unión, el complemento, y cuántos estados se alcanzan en cada ejemplo.

$ make test
test_languages: ok
test_dfa: ok (6 autómatas, 8191 cadenas cada uno)
test_product: ok
Todas las pruebas pasaron.

Los archivos de machines/ son:

Archivo Lenguaje Estados
even_ones.dfa Cantidad par de unos 2
ends_01.dfa Termina en 01\mathtt{01} 3
contains_101.dfa Contiene 101\mathtt{101} 4
multiple_of_3.dfa Múltiplos de 3 en binario 3
starts_with_1.dfa Empieza con 1\mathtt{1}, con estado trampa 3
turnstile.dfa Secuencias que dejan bloqueado el torniquete 2

Para experimentar, copien uno, cámbienle una transición y vuelvan a correr run_dfa con las mismas cadenas. Si rompen la definición, show_dfa les dirá qué falta.

En dfa.h, δ\delta es un std::map con los nombres de los estados como cadenas. Se eligió así para que el código se lea como la definición, y no por velocidad: cada paso busca en el mapa comparando nombres. Para los ejemplos del capítulo sobra.

El laboratorio

En lab/dfa_sim está el enunciado, un esqueleto y los casos. El problema es escribir un simulador: la entrada es un DFA en formato .dfa seguido de una lista de cadenas, y la salida es acepta o rechaza por cada una.

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

dfa.h ya trae una función que simula, y pueden leerla. El trabajo del laboratorio es otro: leer el formato completo, con el bloque de cadenas, y pasar los casos de borde. Por eso solution.cpp se escribe sin incluir dfa.h. Los casos incluyen la cadena vacía, un DFA sin estados de aceptación, uno que acepta todo, estados inalcanzables y tres entradas grandes. Lean las cadenas con std::getline: una línea vacía es la cadena ε\varepsilon, y >> se la salta. El simulador que escriban les servirá las semanas siguientes para probar sus propios autómatas.

Resumen

  • Una cadena es una secuencia finita de símbolos de un alfabeto Σ\Sigma. La cadena vacía ε\varepsilon tiene longitud 0. Σ∗\Sigma^* es el conjunto de todas las cadenas: es infinito, y se puede listar.
  • Las cadenas se definen por casos, ε\varepsilon o xaxa, y las propiedades se demuestran por inducción sobre la longitud, quitando el último símbolo. El caso base es ε\varepsilon.
  • Un lenguaje es un conjunto de cadenas. ∅\emptyset no tiene ninguna, {ε}\{\varepsilon\} tiene una, y ε\varepsilon es una cadena y no un lenguaje. ∅A=∅\emptyset A = \emptyset, {ε}A=A\{\varepsilon\}A = A y ∅∗={ε}\emptyset^* = \{\varepsilon\}.
  • Las operaciones sobre lenguajes son unión, intersección, complemento, concatenación y estrella. A∗A^* siempre contiene a ε\varepsilon.
  • Un problema de decisión es un lenguaje: el de las entradas con respuesta sí. Hay que fijar cómo se escribe la entrada.
  • Los programas se pueden listar y los lenguajes no: hay lenguajes que ningún programa decide. El argumento no dice cuáles. Eso llega en la semana 9.
  • Un DFA es M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F). La función δ\delta es total y da un solo estado: una flecha por cada estado y cada símbolo. El diagrama y la tabla de transiciones dicen lo mismo.
  • δ∗(q,w)\delta^*(q, w) es el estado al que se llega desde qq leyendo ww: δ∗(q,ε)=q\delta^*(q, \varepsilon) = q y δ∗(q,xa)=δ(δ∗(q,x),a)\delta^*(q, xa) = \delta(\delta^*(q, x), a). MM acepta ww si δ∗(q0,w)∈F\delta^*(q_0, w) \in F, y reconoce el lenguaje L(M)L(M) de las cadenas que acepta. Solo cuenta el estado final.
  • Diseñar un DFA es decidir qué recordar: cada estado es un hecho sobre lo leído. Demostrar que es correcto es probar una afirmación por estado, por inducción sobre la longitud.
  • Lo que “ya perdió” va a un estado trampa. No se dejan transiciones sin definir.
  • Un lenguaje es regular si algún DFA lo reconoce.
  • La construcción del producto corre dos DFA a la vez con estados (p,q)(p, q). Con F=F1×F2F = F_1 \times F_2 reconoce la intersección, y con los pares donde alguno acepta, la unión. Tiene ∣Q1∣⋅∣Q2∣|Q_1| \cdot |Q_2| estados, y no todos son siempre alcanzables.
  • El complemento se obtiene cambiando FF por Q−FQ - F. Funciona porque δ\delta es total.
  • Los lenguajes regulares son cerrados bajo unión, intersección y complemento.

Ejercicios

  1. Sea w=01101w = \mathtt{01101}. Escriban todos sus prefijos, todos sus sufijos y todas sus subcadenas distintas, y cuéntenlas. Comprueben con build/strings_demo 01101. ¿Qué cadena binaria de longitud 5 tiene menos subcadenas distintas, y cuántas tiene?
  2. ¿Cuántas cadenas tiene {ε}\{\varepsilon\}? ¿Y ∅\emptyset? Calculen ∅∗\emptyset^*, {ε}∗\{\varepsilon\}^*, ∅∪{ε}\emptyset \cup \{\varepsilon\}, ∅{ε}\emptyset\{\varepsilon\} y ({ε}∪{0})2(\{\varepsilon\} \cup \{\mathtt{0}\})^2, y expliquen cada resultado con la definición. Después modifiquen languages_demo.cpp para comprobarlos.
  3. Sean A={ε,0}A = \{\varepsilon, \mathtt{0}\} y B={1,01}B = \{\mathtt{1}, \mathtt{01}\}. Calculen ABAB, BABA, A2A^2 y las cadenas de B∗B^* de longitud a lo sumo 4. ¿Cuántas cadenas tiene ABAB, y por qué no son ∣A∣⋅∣B∣|A| \cdot |B|? Den dos lenguajes de tres cadenas cada uno cuya concatenación tenga nueve, y otros dos cuya concatenación tenga menos.
  4. Definan el reverso por casos: εR=ε\varepsilon^R = \varepsilon y (xa)R=a(xR)(xa)^R = a(x^R). Demuestren por inducción sobre ∣v∣|v| que (uv)R=vRuR(uv)^R = v^Ru^R. Digan en qué paso usan que la concatenación es asociativa y en cuál que ε\varepsilon es su neutro. Después demuestren que (wR)R=w(w^R)^R = w.
  5. Escriban como lenguaje cada problema, diciendo el alfabeto y cómo se representa la entrada: (a) ¿es nn un cuadrado perfecto?; (b) ¿está ordenada esta lista de números?; (c) ¿tiene este grafo un ciclo? En cada uno, den una cadena del lenguaje, una que no esté porque la respuesta es no, y una que no esté porque está mal formada.
  6. Den un DFA para las cadenas sobre {a,b}\{\mathtt{a}, \mathtt{b}\} que no contienen aa. Escriban qué recuerda cada estado, la tabla y el archivo .dfa, y síganlo con run_dfa para abab, baab y la cadena vacía. ¿Cuál es el estado trampa?
  7. Diseñen un DFA para cada lenguaje sobre {0,1}\{\mathtt{0}, \mathtt{1}\}, con la tabla de lo que recuerda cada estado: (a) las cadenas de longitud impar; (b) las que empiezan y terminan con el mismo símbolo; (c) las que tienen un 1\mathtt{1} en la penúltima posición; (d) las que no terminan en 01\mathtt{01}. Para (d), ¿pueden reutilizar un autómata del capítulo?
  8. Demuestren que el autómata de machines/contains_101.dfa reconoce el lenguaje BB, con las cuatro afirmaciones de su tabla de estados. ¿En qué caso del paso inductivo se usa que q1q_1 con 1\mathtt{1} se queda en q1q_1?
  9. Demuestren que el autómata de machines/multiple_of_3.dfa cumple δ∗(r0,w)=rk\delta^*(r_0, w) = r_k, donde kk es el resto de val(w)\mathrm{val}(w) entre 3. Después diseñen el DFA de los múltiplos de 5 en binario. ¿Cuántos estados tiene? ¿Qué cambia si el número se lee con el bit menos significativo primero? Diseñen ese autómata para los múltiplos de 3.
  10. Con product, construyan el autómata de las cadenas que contienen 101\mathtt{101} y son múltiplo de 3. ¿Cuántos estados tiene, y cuántos son alcanzables? Sigan a mano la cadena 10101\mathtt{10101} en el producto y comprueben con run_dfa. Después repitan con Termina en 01 y Empieza con 1: expliquen cada par inalcanzable como dos hechos que se contradicen.
  11. La diferencia A−BA - B y la diferencia simétrica (las cadenas que están en exactamente uno de los dos) también salen del producto. Den el FF de cada una y demuestren una de las dos con la cadena de equivalencias de este capítulo. ¿Cuántos conjuntos FF distintos se pueden elegir en el producto de la cuadrícula de 6 estados?
  12. Si MM tiene nn estados, ¿cuántos tiene el DFA del complemento de L(M)L(M)? Den un lenguaje regular AA sobre {0,1}\{\mathtt{0}, \mathtt{1}\} tal que AA y su complemento sean infinitos, y otro tal que AA sea infinito y su complemento finito. ¿Puede un DFA con todos sus estados alcanzables y F≠∅F \neq \emptyset reconocer el lenguaje ∅\emptyset?
  13. Para programar. Agreguen a dfa.h una función que decida si L(M)=∅L(M) = \emptyset, sin probar cadenas: un DFA acepta alguna cadena si y solo si algún estado de aceptación es alcanzable. Con ella y con el producto, escriban un programa que decida si dos DFA reconocen el mismo lenguaje, y úsenlo para comparar el autómata de 7 estados de Termina en 01, el que recuerda los dos últimos símbolos, con el de 3. Este problema vuelve en el laboratorio de la semana 9.