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

Apuntes · Capítulo 4Lenguajes regulares

Lo que un autómata finito no puede hacer

Lo que un autómata finito no puede hacer

Tres semanas seguidas agrandaron la clase de los lenguajes regulares sin cambiarla. En la semana 1 la definimos con los DFA. En la semana 2 le dimos a la máquina la capacidad de adivinar, y la construcción de subconjuntos mostró que un NFA no reconoce nada que un DFA no reconozca. En la semana 3 cambiamos las máquinas por descripciones, y el teorema de Kleene mostró que las expresiones regulares describen exactamente los mismos lenguajes. Unión, intersección, complemento, concatenación, estrella y reverso tampoco sacan de la clase.

Una clase tan estable podría hacer pensar que todo lenguaje razonable es regular. No es así, y esta semana lo demostramos. Es el primer resultado de imposibilidad del curso, y conviene mirar bien su forma, porque se repite en cada parte: no decimos “nadie ha encontrado un DFA para este lenguaje”, sino “ningún DFA lo reconoce, tenga los estados que tenga”. Para afirmar algo sobre todos los autómatas a la vez no sirve probar con algunos. Hace falta un argumento que use lo único que todos tienen en común: una cantidad finita de estados.

Hay dos herramientas. La sesión A presenta el lema de bombeo, la clásica: toda cadena larga de un lenguaje regular tiene un tramo que se puede repetir. La sesión B presenta las cadenas distinguibles, que suelen dar demostraciones más cortas y además cuentan estados: con ellas pagamos una deuda de la semana 2, que el DFA de “el kk-ésimo símbolo desde el final es 1\mathtt{1}” necesita 2k2^k estados. De esa misma idea salen el teorema de Myhill-Nerode, que dice exactamente cuántos estados necesita un lenguaje, y un algoritmo para minimizar cualquier DFA. Con esto se cierra la parte 1.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Contar sin tope y Un estado que se repite. Antes de la sesión B, Cadenas distinguibles hasta el primer teorema. Con eso llegan con la idea de las dos herramientas.

En clase: Sesión A, de Contar sin tope a Lo que el lema no dice. Sesión B, de Cadenas distinguibles a El DFA mínimo es único.

Después de clase: el Resumen y los Ejercicios. El código de la semana, si van a hacer el ejercicio opcional de minimización. Opcional: Streaming: una cota inferior de memoria, que no entra en las evaluaciones, y las lecturas de apoyo del recuadro siguiente.

Lectura. Sesión A: Sipser, sec. 1.4 (Nonregular Languages). Sesión B: Sipser deja Myhill-Nerode y la minimización como problemas del capítulo 1, sin desarrollarlos; Erickson, Models of Computation, nota 3, sección sobre conjuntos distinguidores (fooling sets). Para la sesión B, estos apuntes son el texto principal.

Código. Los programas de este capítulo están en code/week-04. 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 ejercicio opcional de laboratorio está en lab/minimize_dfa.

Contar sin tope

El lenguaje de esta semana ya apareció en la semana 1:

B={ 0n1n:n≥0 }={ε,01,0011,000111,…}B = \{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} = \{\varepsilon, \mathtt{01}, \mathtt{0011}, \mathtt{000111}, \ldots\}

Algunos ceros, y después exactamente la misma cantidad de unos. Para decidir si una cadena está en BB leyendo de izquierda a derecha hay que recordar cuántos ceros hubo, y esa cantidad no tiene tope.

Intentemos construir un DFA de todos modos. Con el método de la semana 1, cada estado es un hecho sobre lo leído: “van 0 ceros”, “van 1”, “van 2”, “van 3”. Después, por cada cantidad, estados que descuentan los unos. En algún momento hay que parar de agregar estados, y lo natural es cerrar con uno que diga “van 3 o más”. Ese intento está en machines/count_attempt.dfa:

$ build/show_dfa machines/count_attempt.dfa
Q  = {z0, z1, z2, z3, u2, u1, u0, x}
Σ  = {0, 1}
q0 = z0
F  = {z0, u0}

     δ   0   1
-> * z0  z1  x
     z1  z2  u0
     z2  z3  u1
     z3  z3  u2
     u2  x   u1
     u1  x   u0
   * u0  x   x
     x   x   x

estados alcanzables desde z0: 8 de 8

Los estados z0 a z3 cuentan ceros, u2, u1 y u0 cuentan los unos que faltan, y x es el estado trampa. Con las cadenas cortas acierta:

$ build/run_dfa machines/count_attempt.dfa 000111 0010
w = 000111
  z0 -0-> z1 -0-> z2 -0-> z3 -1-> u2 -1-> u1 -1-> u0
  termina en u0, que está en F: acepta
w = 0010
  z0 -0-> z1 -0-> z2 -1-> u1 -0-> x
  termina en x, que no está en F: rechaza

Y con las largas se equivoca en los dos sentidos:

$ build/run_dfa machines/count_attempt.dfa 00000111 00001111
w = 00000111
  z0 -0-> z1 -0-> z2 -0-> z3 -0-> z3 -0-> z3 -1-> u2 -1-> u1 -1-> u0
  termina en u0, que está en F: acepta
w = 00001111
  z0 -0-> z1 -0-> z2 -0-> z3 -0-> z3 -1-> u2 -1-> u1 -1-> u0 -1-> x
  termina en x, que no está en F: rechaza

Acepta 0513\mathtt{0}^5\mathtt{1}^3, que no está en BB, y rechaza 0414\mathtt{0}^4\mathtt{1}^4, que sí está. La causa está a la vista en la primera ejecución: después del tercer cero la máquina se queda dando vueltas en z3, y desde ahí ya no sabe si leyó tres ceros, cinco o cien.

Se puede arreglar ese autómata agregando estados: contar hasta 4, hasta 10, hasta 1000. Cada arreglo acierta con más cadenas y deja el mismo problema un poco más lejos. Pero de ahí no se concluye nada. Que este diseño falle, o que a nadie se le ocurra uno mejor, no demuestra que no exista: podría haber un autómata que no cuente los ceros y reconozca BB con algún truco que no vemos. En la semana 1 ya pasó algo así, cuando para los múltiplos de 3 no hizo falta recordar el número, sino solo su resto.

Error común. Dar como demostración “un DFA no puede contar” o “no se me ocurre ningún DFA”. La primera frase es la conclusión, no el argumento, y además es falsa tal como está: un DFA cuenta sin problemas hasta cualquier tope fijo, o módulo cualquier número. La segunda habla de quien busca, no del lenguaje. Una demostración de que BB no es regular tiene que empezar por “sea MM un DFA cualquiera” y terminar con una cadena concreta en la que MM se equivoca.

Un estado que se repite

Lo que le pasó al intento anterior le pasa a todo DFA, y es lo único que hay que entender esta semana.

Un DFA con pp estados que lee una cadena de pp símbolos o más pasa por p+1p + 1 estados o más, contando el inicial. No hay tantos estados distintos: alguno se repite. Entre la primera visita a ese estado y la segunda, la máquina leyó un tramo de la cadena y volvió al mismo lugar. Dio una vuelta por un ciclo.

Ahora, el estado es todo lo que la máquina recuerda. Si está otra vez en el mismo estado, no sabe si dio la vuelta o no, y lo que haga después será igual en los dos casos. Entonces podemos quitar ese tramo de la cadena, o repetirlo dos, tres o cien veces, y la máquina terminará en el mismo estado final que con la cadena original.

El programa pump hace exactamente eso con un DFA de verdad. Recibe un autómata y una cadena con al menos tantos símbolos como estados, busca el primer estado que se repite y parte la cadena en tres: xx, lo leído antes de la primera visita; yy, lo leído entre las dos visitas; zz, el resto. Con el autómata de los múltiplos de 3 de la semana 1, que tiene 3 estados, y la cadena 10101\mathtt{10101}:

$ build/pump machines/multiple_of_3.dfa 10101
p = |Q| = 3, w = 10101, |w| = 5
  r0 -1-> r1 -0-> r2 -1-> r2 -0-> r1 -1-> r0
primer estado que se repite: r2, después de leer 2 y 3 símbolos
x = 10, y = 1, z = 01    |y| = 1 > 0, |xy| = 3 ≤ 3
  i = 0: 1001 termina en r0, acepta
  i = 1: 10101 termina en r0, acepta
  i = 2: 101101 termina en r0, acepta
  i = 3: 1011101 termina en r0, acepta
  i = 4: 10111101 termina en r0, acepta
todas terminan igual que w

La ejecución pasa por r2 después de leer 10\mathtt{10}, y otra vez después de leer 101\mathtt{101}: el tercer símbolo, un 1\mathtt{1}, la dejó donde estaba. Ese símbolo es yy. Las cinco cadenas de la lista son xyizx y^i z para ii de 0 a 4, y las cinco terminan en r0. En efecto, son 9, 21, 45, 93 y 189 en binario, todos múltiplos de 3. El autómata no puede distinguirlas: en todas hace el mismo recorrido, salvo el número de vueltas en r2.

Animación del autómata de los múltiplos de 3, con estados r₀, r₁ y r₂, leyendo las cadenas que salen de bombear 10101. Arriba está la cadena partida en tres tramos de colores: x = 10, y = 1, z = 01. El autómata: r₀ es inicial y de aceptación, con un bucle con 0; de r₀ a r₁ con 1 y de vuelta con 1; de r₁ a r₂ con 0 y de vuelta con 0; r₂ tiene un bucle con 1, que es el ciclo. Primer paso: la división que encuentra pump. Segundo paso, i = 1, la cadena original 10101: una ficha recorre r₀, r₁, r₂, da una vuelta por el bucle de r₂, y vuelve por r₁ a r₀. Tercer paso, i = 0, la cadena 1001: el mismo recorrido sin ninguna vuelta en r₂. Cuarto paso, i = 2, la cadena 101101: el mismo recorrido con dos vueltas en r₂. Debajo se van anotando los resultados: las tres terminan en r₀ y se aceptanAnimación del autómata de los múltiplos de 3, con estados r₀, r₁ y r₂, leyendo las cadenas que salen de bombear 10101. Arriba está la cadena partida en tres tramos de colores: x = 10, y = 1, z = 01. El autómata: r₀ es inicial y de aceptación, con un bucle con 0; de r₀ a r₁ con 1 y de vuelta con 1; de r₁ a r₂ con 0 y de vuelta con 0; r₂ tiene un bucle con 1, que es el ciclo. Primer paso: la división que encuentra pump. Segundo paso, i = 1, la cadena original 10101: una ficha recorre r₀, r₁, r₂, da una vuelta por el bucle de r₂, y vuelve por r₁ a r₀. Tercer paso, i = 0, la cadena 1001: el mismo recorrido sin ninguna vuelta en r₂. Cuarto paso, i = 2, la cadena 101101: el mismo recorrido con dos vueltas en r₂. Debajo se van anotando los resultados: las tres terminan en r₀ y se aceptan
Bombear es dar más o menos vueltas por el ciclo. El recorrido antes y después de r₂ es el mismo, y por eso las tres cadenas terminan en el mismo estado.

Para un lenguaje regular eso no es un defecto. Los múltiplos de 3 sí tienen esa propiedad. El problema aparece cuando el lenguaje no la tiene, y el intento de la sección anterior lo muestra:

$ build/pump machines/count_attempt.dfa 00000000111
p = |Q| = 8, w = 00000000111, |w| = 11
  z0 -0-> z1 -0-> z2 -0-> z3 -0-> z3 -0-> z3 -0-> z3 -0-> z3 -0-> z3 -1-> u2 -1-> u1 -1-> u0
primer estado que se repite: z3, después de leer 3 y 4 símbolos
x = 000, y = 0, z = 0000111    |y| = 1 > 0, |xy| = 4 ≤ 8
  i = 0: 0000000111 termina en u0, acepta
  i = 1: 00000000111 termina en u0, acepta
  i = 2: 000000000111 termina en u0, acepta
  i = 3: 0000000000111 termina en u0, acepta
  i = 4: 00000000000111 termina en u0, acepta
todas terminan igual que w

El ciclo es la vuelta en z3, y yy es un cero. Repetirlo o quitarlo cambia la cantidad de ceros sin cambiar la de unos, y el autómata acepta todas esas cadenas, aunque ninguna tiene tantos ceros como unos. Eso no es un accidente de este diseño. Cualquier DFA, con una cadena de BB suficientemente larga, tiene que repetir un estado mientras todavía está leyendo ceros, y entonces acepta cadenas que no están en BB.

Idea clave. En un DFA con pp estados, toda ejecución de pp pasos o más repite un estado. El tramo de la cadena leído entre las dos visitas se puede quitar o repetir sin que cambie el estado final.

El lema de bombeo

El lema dice lo anterior sin mencionar ningún autómata: es una propiedad que tienen todos los lenguajes regulares. “Bombear” una cadena es repetir un tramo suyo.

Lema de bombeo (pumping lemma). Si AA es un lenguaje regular, existe un número p≥1p \geq 1, la longitud de bombeo (pumping length) de AA, tal que toda cadena s∈As \in A con ∣s∣≥p|s| \geq p se puede dividir en tres partes, s=xyzs = xyz, que cumplen:

  1. xyiz∈Axy^iz \in A para todo i≥0i \geq 0;
  2. ∣y∣>0|y| > 0;
  3. ∣xy∣≤p|xy| \leq p.

Cada condición tiene su papel.

  • La primera es el bombeo: yy se puede repetir cualquier número de veces. Con i=1i = 1 sale ss. Con i=0i = 0 sale xzxz, la cadena sin yy: también tiene que estar en AA. Con i=2i = 2 sale xyyzxyyz.
  • La segunda dice que yy no es vacía. Sin ella el lema no diría nada: con y=εy = \varepsilon, todas las cadenas xyizxy^iz son la misma ss.
  • La tercera dice dónde está el tramo que se repite: dentro de los primeros pp símbolos de ss. Es la que hace cómodo usar el lema, porque limita lo que yy puede contener.

Nada impide que xx o zz sean vacías.

El lema solo habla de las cadenas de longitud al menos pp. Sobre las más cortas no dice nada. Por eso un lenguaje finito lo cumple sin esfuerzo: si su cadena más larga mide mm, basta tomar p=m+1p = m + 1, y no hay ninguna cadena de AA a la que se le exija algo.

Demostración. Por construcción de la división, con el principio del palomar. Como AA es regular, hay un DFA M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) con L(M)=AL(M) = A. Tomamos p=∣Q∣p = |Q|, el número de estados.

Sea s=s1s2⋯sns = s_1s_2 \cdots s_n una cadena de AA con n≥pn \geq p, y sea r0,r1,…,rnr_0, r_1, \ldots, r_n la ejecución de MM con ss: r0=q0r_0 = q_0 y rk=δ(rk−1,sk)r_k = \delta(r_{k-1}, s_k). Como MM acepta ss, rn∈Fr_n \in F.

Un estado se repite pronto. Miremos solo los primeros p+1p + 1 estados de la ejecución: r0,r1,…,rpr_0, r_1, \ldots, r_p. Existen, porque n≥pn \geq p. Son p+1p + 1 estados y MM tiene solo pp distintos, así que por el principio del palomar dos de ellos son el mismo: hay índices jj y ll con 0≤j<l≤p0 \leq j < l \leq p y rj=rlr_j = r_l.

La división. Partimos ss en los dos lugares donde aparece ese estado:

x=s1⋯sj,y=sj+1⋯sl,z=sl+1⋯sn.x = s_1 \cdots s_j, \qquad y = s_{j+1} \cdots s_l, \qquad z = s_{l+1} \cdots s_n.

Por la definición de la ejecución, xx lleva de q0q_0 a rjr_j, yy lleva de rjr_j a rlr_l, y zz lleva de rlr_l a rnr_n. Como rl=rjr_l = r_j, llamemos rr a ese estado:

δ∗(q0,x)=r,δ∗(r,y)=r,δ∗(r,z)=rn∈F.\delta^*(q_0, x) = r, \qquad \delta^*(r, y) = r, \qquad \delta^*(r, z) = r_n \in F.
Figura en dos partes. Arriba, la ejecución con s dibujada estado por estado: r₀, r₁, y así hasta rₙ, que es de aceptación. Un corchete abarca los primeros p + 1 estados, de r₀ a r_p, con la nota de que M solo tiene p estados distintos y por eso dos son el mismo; esos dos, r_j y r_l, están resaltados. Debajo, la cadena cortada en esas dos visitas: x, los símbolos 1 a j, va de r₀ a r_j; y, los símbolos j + 1 a l, va de r_j a r_l; y z, los símbolos l + 1 a n, va de r_l a rₙ, con las anotaciones |y| = l − j > 0 y |xy| = l ≤ p. Abajo, la misma ejecución dibujada en el autómata: de q₀ sale una flecha con x hasta el estado r, que es r_j y r_l a la vez; r tiene un bucle con y; y de r sale una flecha con z hasta rₙ, con doble círculo. Una nota dice que la vuelta se puede dar 0, 1, 2 o más vecesFigura en dos partes. Arriba, la ejecución con s dibujada estado por estado: r₀, r₁, y así hasta rₙ, que es de aceptación. Un corchete abarca los primeros p + 1 estados, de r₀ a r_p, con la nota de que M solo tiene p estados distintos y por eso dos son el mismo; esos dos, r_j y r_l, están resaltados. Debajo, la cadena cortada en esas dos visitas: x, los símbolos 1 a j, va de r₀ a r_j; y, los símbolos j + 1 a l, va de r_j a r_l; y z, los símbolos l + 1 a n, va de r_l a rₙ, con las anotaciones |y| = l − j > 0 y |xy| = l ≤ p. Abajo, la misma ejecución dibujada en el autómata: de q₀ sale una flecha con x hasta el estado r, que es r_j y r_l a la vez; r tiene un bucle con y; y de r sale una flecha con z hasta rₙ, con doble círculo. Una nota dice que la vuelta se puede dar 0, 1, 2 o más veces
Como los dos estados son el mismo, el tramo y es una vuelta que empieza y termina en el mismo lugar. Darla i veces no cambia adónde lleva z.

Condición 2. ∣y∣=l−j>0|y| = l - j > 0, porque j<lj < l.

Condición 3. ∣xy∣=l≤p|xy| = l \leq p.

Condición 1. Primero, δ∗(r,yi)=r\delta^*(r, y^i) = r para todo i≥0i \geq 0, por inducción sobre ii. Para i=0i = 0, y0=εy^0 = \varepsilon y δ∗(r,ε)=r\delta^*(r, \varepsilon) = r. Si vale para ii, entonces por el lema de la concatenación de la semana 1,

δ∗(r,yi+1)=δ∗(r,yiy)=δ∗(δ∗(r,yi),y)=δ∗(r,y)=r.\delta^*(r, y^{i+1}) = \delta^*(r, y^iy) = \delta^*(\delta^*(r, y^i), y) = \delta^*(r, y) = r.

Con eso, y otra vez con el lema de la concatenación:

δ∗(q0,xyiz)=δ∗(δ∗(δ∗(q0,x),yi),z)=δ∗(δ∗(r,yi),z)porque δ∗(q0,x)=r=δ∗(r,z)porque δ∗(r,yi)=r=rn∈F\begin{aligned} \delta^*(q_0, xy^iz) &= \delta^*(\delta^*(\delta^*(q_0, x), y^i), z) \\ &= \delta^*(\delta^*(r, y^i), z) && \text{porque } \delta^*(q_0, x) = r \\ &= \delta^*(r, z) && \text{porque } \delta^*(r, y^i) = r \\ &= r_n \in F \end{aligned}

Luego MM acepta xyizxy^iz, es decir, xyiz∈Axy^iz \in A, para todo i≥0i \geq 0. ∎

La demostración es el programa pump de la sección anterior, línea por línea: tomar p=∣Q∣p = |Q|, mirar los primeros p+1p + 1 estados de la ejecución y cortar en la primera repetición. Las pruebas de la semana lo comprueban con siete autómatas y todas las cadenas de longitud entre ∣Q∣|Q| y 11: en cada una, la división que encuentra pump cumple las tres condiciones.

Dos observaciones sobre lo que la demostración da y lo que no.

  • pp no es único. Si pp sirve, cualquier número mayor también sirve: hay menos cadenas a las que exigirles algo, y ∣xy∣≤p|xy| \leq p es más fácil de cumplir. La demostración da p=∣Q∣p = |Q| para un DFA cualquiera de AA. No hace falta conocerlo, y de hecho al usar el lema nunca lo conocemos.
  • La división la decide el autómata. Depende de qué estado se repite, y eso depende de un DFA que no tenemos. El lema solo promete que alguna división funciona.

El lema como un juego

Para demostrar que un lenguaje no es regular, el lema se usa al revés. Si un lenguaje regular tiene siempre la propiedad de bombeo, un lenguaje que no la tiene no puede ser regular. Hay que escribir con cuidado qué significa “no tenerla”, porque el enunciado tiene cuatro cuantificadores encadenados:

A regular  ⟹    existe p≥1 tal quepara toda s∈A con ∣s∣≥pexiste una divisioˊn s=xyz con ∣y∣>0 y ∣xy∣≤p tal quepara todo i≥0,xyiz∈A.\begin{aligned} A \text{ regular} \implies\; & \text{existe } p \geq 1 \text{ tal que} \\ & \text{para toda } s \in A \text{ con } |s| \geq p \\ & \text{existe una división } s = xyz \text{ con } |y| > 0 \text{ y } |xy| \leq p \text{ tal que} \\ & \text{para todo } i \geq 0, \quad xy^iz \in A. \end{aligned}

Al negar la propiedad, cada “existe” se vuelve “para todo” y al revés. AA no tiene la propiedad de bombeo si:

para todo p≥1existe s∈A con ∣s∣≥p tal quepara toda divisioˊn s=xyz con ∣y∣>0 y ∣xy∣≤pexiste i≥0 con xyiz∉A.\begin{aligned} & \text{para todo } p \geq 1 \\ & \text{existe } s \in A \text{ con } |s| \geq p \text{ tal que} \\ & \text{para toda división } s = xyz \text{ con } |y| > 0 \text{ y } |xy| \leq p \\ & \text{existe } i \geq 0 \text{ con } xy^iz \notin A. \end{aligned}

Y si AA no tiene la propiedad, AA no es regular: es el lema, leído por la contrarrecíproca.

Esa alternancia de “para todo” y “existe” se recuerda mejor como un juego entre dos jugadores. Nosotros queremos demostrar que AA no es regular. El adversario sostiene que sí lo es. Lo que en la fórmula es “para todo” lo elige él, y lo que es “existe” lo elegimos nosotros.

Jugada Quién Qué elige
1 El adversario Un número p≥1p \geq 1. Dice que es la longitud de bombeo de AA
2 Nosotros Una cadena s∈As \in A con ∣s∣≥p\lvert s\rvert \geq p. Puede y debe depender de pp
3 El adversario Una división s=xyzs = xyz con ∣y∣>0\lvert y\rvert > 0 y ∣xy∣≤p\lvert xy\rvert \leq p
4 Nosotros Un exponente i≥0i \geq 0. Ganamos si xyiz∉Axy^iz \notin A

Demostrar que AA no es regular es dar una estrategia ganadora: una manera de jugar que gana sin importar qué haga el adversario. En la práctica eso quiere decir:

  • No conocemos pp. La cadena ss se da como una fórmula en la que aparece pp, por ejemplo 0p1p\mathtt{0}^p\mathtt{1}^p, y el argumento tiene que valer para cualquier valor.
  • No elegimos la división. Lo único que sabemos de xx, yy, zz son las dos condiciones que el adversario está obligado a respetar: ∣y∣>0|y| > 0 y ∣xy∣≤p|xy| \leq p. La demostración tiene que cubrir todas las divisiones que las cumplen.
  • Sí elegimos ss e ii, y ahí está todo el trabajo. Una buena ss es una en la que la condición ∣xy∣≤p|xy| \leq p deja al adversario sin margen: por ejemplo, una que empieza con pp símbolos iguales, de modo que yy solo pueda estar hecha de ese símbolo.

El programa pumping_game juega una partida completa para un valor concreto de pp. Usa nuestra cadena y nuestro exponente, y recorre todas las divisiones permitidas:

$ build/pumping_game 0n1n 3
L = { 0^n 1^n : n ≥ 0 }
el adversario elige p = 3
nosotros elegimos s = 000111, con |s| = 6 y s ∈ L
nuestro exponente: i = 2
divisiones posibles con |xy| ≤ 3 y |y| > 0: 6
  x   y    z      x y^i z
  ε   0    00111  0000111    ∉ L
  ε   00   0111   00000111   ∉ L
  ε   000  111    000000111  ∉ L
  0   0    0111   0000111    ∉ L
  0   00   111    00000111   ∉ L
  00  0    111    0000111    ∉ L
en las 6 divisiones la cadena bombeada sale de L

Con ∣s∣≥p|s| \geq p, las divisiones permitidas son p(p+1)/2p(p+1)/2: aquí, 6. El programa no demuestra nada, porque juega con un solo valor de pp y la demostración tiene que valer para todos. Sirve para lo contrario: para ver qué puede hacer el adversario y encontrar el error en un argumento antes de escribirlo.

Error común. Elegir uno mismo la división: “sea x=0p−1x = \mathtt{0}^{p-1}, y=0y = \mathtt{0}, z=1pz = \mathtt{1}^p; entonces xy2z∉Axy^2z \notin A”. Eso solo muestra que una división falla, y el lema promete que alguna funciona, no que todas. La división es la jugada del adversario. El otro error gemelo es usar una cadena que no depende de pp, como s=000111s = \mathtt{000111}: si el adversario dice p=7p = 7, esa cadena es más corta que pp y el lema no dice nada sobre ella.

Cinco demostraciones

Las cinco siguen el mismo esquema, con las cuatro jugadas a la vista. En cada una hay que comprobar tres cosas de nuestra cadena: que está en el lenguaje, que mide al menos pp, y que con cualquier división permitida hay un exponente que la saca.

El lenguaje 0ⁿ1ⁿ

Teorema. B={ 0n1n:n≥0 }B = \{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} no es regular.

Demostración. Por contradicción, con el lema de bombeo. Supongamos que BB es regular.

Jugada 1: el adversario elige pp. Por el lema, BB tiene una longitud de bombeo p≥1p \geq 1. No sabemos cuánto vale.

Jugada 2: elegimos ss. Tomamos s=0p1ps = \mathtt{0}^p\mathtt{1}^p. Está en BB, con n=pn = p, y ∣s∣=2p≥p|s| = 2p \geq p.

Jugada 3: el adversario elige la división. Por el lema, s=xyzs = xyz con ∣y∣>0|y| > 0 y ∣xy∣≤p|xy| \leq p. No sabemos cuál es, pero esas dos condiciones dicen bastante. Los primeros pp símbolos de ss son todos ceros, y xyxy es un prefijo de ss de longitud a lo sumo pp: entonces xx e yy están hechas solo de ceros. Es decir,

x=0a,y=0k,z=0p−a−k1p,con k≥1 y a+k≤p.x = \mathtt{0}^a, \qquad y = \mathtt{0}^k, \qquad z = \mathtt{0}^{p-a-k}\mathtt{1}^p, \qquad \text{con } k \geq 1 \text{ y } a + k \leq p.

Todas las divisiones permitidas son de esta forma, para algún aa y algún kk.

Jugada 4: elegimos ii. Tomamos i=2i = 2. Entonces

xy2z=0a 02k 0p−a−k1p=0p+k1p.xy^2z = \mathtt{0}^a\,\mathtt{0}^{2k}\,\mathtt{0}^{p-a-k}\mathtt{1}^p = \mathtt{0}^{p+k}\mathtt{1}^p.

Como k≥1k \geq 1, esta cadena tiene más ceros que unos: no está en BB.

Pero la condición 1 del lema dice que xy2z∈Bxy^2z \in B. Es una contradicción, y vino de suponer que BB es regular. ∎

Es la partida que pumping_game jugó arriba con p=3p = 3: en las 6 divisiones, yy es 0\mathtt{0}, 00\mathtt{00} o 000\mathtt{000}, y la cadena bombeada tiene 4, 5 o 6 ceros y 3 unos.

Figura en dos partes. Arriba, las cuatro jugadas en dos carriles: el del adversario, que elige lo que en la fórmula es para todo, y el nuestro, que elige lo que es existe. Jugada 1, el adversario elige p ≥ 1. Jugada 2, nosotros elegimos s = 0ᵖ1ᵖ. Jugada 3, el adversario elige una división s = xyz con |y| > 0 y |xy| ≤ p. Jugada 4, nosotros elegimos i = 2. Abajo, tres filas con la cadena dibujada como bloques. La primera es s: p ceros seguidos de p unos. La segunda es la división: x = 0ᵃ e y = 0ᵏ caben antes de una línea punteada que marca el final de los ceros, porque |xy| ≤ p, y z es el resto de los ceros con los p unos. La tercera es xy²z: el bloque y aparece dos veces, y la cadena es 0ᵖ⁺ᵏ1ᵖ, que no está en BFigura en dos partes. Arriba, las cuatro jugadas en dos carriles: el del adversario, que elige lo que en la fórmula es para todo, y el nuestro, que elige lo que es existe. Jugada 1, el adversario elige p ≥ 1. Jugada 2, nosotros elegimos s = 0ᵖ1ᵖ. Jugada 3, el adversario elige una división s = xyz con |y| > 0 y |xy| ≤ p. Jugada 4, nosotros elegimos i = 2. Abajo, tres filas con la cadena dibujada como bloques. La primera es s: p ceros seguidos de p unos. La segunda es la división: x = 0ᵃ e y = 0ᵏ caben antes de una línea punteada que marca el final de los ceros, porque |xy| ≤ p, y z es el resto de los ceros con los p unos. La tercera es xy²z: el bloque y aparece dos veces, y la cadena es 0ᵖ⁺ᵏ1ᵖ, que no está en B
La partida de 0ⁿ1ⁿ. La cadena 0ᵖ1ᵖ obliga al adversario a tomar y entre los ceros, y entonces repetirla desequilibra la cadena.

Dos comentarios. Con i=0i = 0 también se gana: xz=0p−k1pxz = \mathtt{0}^{p-k}\mathtt{1}^p tiene menos ceros que unos. Y la condición 3 hizo casi todo el trabajo. Sin ella, el adversario podría elegir una yy con ceros y unos, o solo con unos, y habría que tratar esos casos aparte. Se puede, pero es más largo y es fácil olvidar uno.

Igual número de ceros y unos

Teorema. E={ w∈{0,1}∗:w tiene tantos ceros como unos }E = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : w \text{ tiene tantos ceros como unos} \,\} no es regular.

Aquí los símbolos pueden venir en cualquier orden: 0110\mathtt{0110} y 1010\mathtt{1010} están en EE.

Demostración. Por contradicción, con el lema de bombeo. Supongamos que EE es regular.

Jugada 1. El adversario elige p≥1p \geq 1.

Jugada 2. Elegimos s=0p1ps = \mathtt{0}^p\mathtt{1}^p, la misma cadena de antes. Tiene pp ceros y pp unos, así que está en EE, y ∣s∣=2p≥p|s| = 2p \geq p.

Jugada 3. El adversario elige s=xyzs = xyz con ∣y∣>0|y| > 0 y ∣xy∣≤p|xy| \leq p. Como antes, xyxy cae dentro de los primeros pp símbolos, que son ceros: y=0ky = \mathtt{0}^k con k≥1k \geq 1.

Jugada 4. Elegimos i=2i = 2. La cadena xy2z=0p+k1pxy^2z = \mathtt{0}^{p+k}\mathtt{1}^p tiene p+kp + k ceros y pp unos, con k≥1k \geq 1: no está en EE. Contradicción con la condición 1. ∎

La demostración es la misma porque la cadena es la misma. Lo que cambia es que aquí importa cuál se elige. Una cadena igual de natural, s=(01)ps = (\mathtt{01})^p, también está en EE y mide 2p2p. Con ella perdemos:

$ build/pumping_game iguales-mal 3
L = { w : w tiene tantos 0 como 1 }
el adversario elige p = 3
nosotros elegimos s = 010101, con |s| = 6 y s ∈ L
nuestro exponente: i = 2
divisiones posibles con |xy| ≤ 3 y |y| > 0: 6
  x   y    z      x y^i z
  ε   0    10101  0010101    ∉ L
  ε   01   0101   01010101   ∈ L: el adversario resiste
  ε   010  101    010010101  ∉ L
  0   1    0101   0110101    ∉ L
  0   10   101    01010101   ∈ L: el adversario resiste
  01  0    101    0100101    ∉ L
el adversario tiene 2 divisiones que resisten: con esta jugada no se demuestra nada

El adversario elige x=εx = \varepsilon, y=01y = \mathtt{01} y z=(01)p−1z = (\mathtt{01})^{p-1}. Es una jugada permitida si p≥2p \geq 2, porque ∣xy∣=2|xy| = 2. Y entonces xyiz=(01)p−1+ixy^iz = (\mathtt{01})^{p-1+i} está en EE para todo ii: no hay exponente que nos salve. Eso no demuestra que EE sea regular. Demuestra que con esa cadena no se llega a ninguna contradicción, y que hay que buscar otra.

Error común. Concluir algo de una partida perdida. Si para la cadena que eligieron el adversario tiene una división que resiste, lo único que saben es que eligieron mal. La cadena buena es la que usa la condición ∣xy∣≤p|xy| \leq p para arrinconar a yy.

El lenguaje ww

Teorema. D={ ww:w∈{0,1}∗ }D = \{\, ww : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\} no es regular.

DD tiene las cadenas que son una mitad repetida: 0101\mathtt{0101}, con w=01w = \mathtt{01}, y 110110\mathtt{110110}, con w=110w = \mathtt{110}. Para reconocerlas habría que recordar la primera mitad entera.

Demostración. Por contradicción, con el lema de bombeo. Supongamos que DD es regular.

Jugada 1. El adversario elige p≥1p \geq 1.

Jugada 2. Elegimos s=0p10p1s = \mathtt{0}^p\mathtt{1}\mathtt{0}^p\mathtt{1}. Está en DD, con w=0p1w = \mathtt{0}^p\mathtt{1}, y ∣s∣=2p+2≥p|s| = 2p + 2 \geq p.

Jugada 3. El adversario elige s=xyzs = xyz con ∣y∣>0|y| > 0 y ∣xy∣≤p|xy| \leq p. Los primeros pp símbolos de ss son ceros, así que y=0ky = \mathtt{0}^k con 1≤k≤p1 \leq k \leq p, y está dentro del primer bloque de ceros.

Jugada 4. Elegimos i=2i = 2:

xy2z=0p+k10p1.xy^2z = \mathtt{0}^{p+k}\mathtt{1}\mathtt{0}^p\mathtt{1}.

Falta ver que esta cadena no está en DD. Supongamos que sí: xy2z=uuxy^2z = uu para alguna cadena uu. La cadena termina en 1\mathtt{1}, así que uu termina en 1\mathtt{1}. La cadena tiene exactamente dos unos, y como las dos mitades son iguales, cada una tiene exactamente uno. Entonces uu tiene un solo 1\mathtt{1} y está al final: u=0m1u = \mathtt{0}^m\mathtt{1} para algún mm, y

uu=0m10m1.uu = \mathtt{0}^m\mathtt{1}\mathtt{0}^m\mathtt{1}.

Comparando con 0p+k10p1\mathtt{0}^{p+k}\mathtt{1}\mathtt{0}^p\mathtt{1}: el primer bloque de ceros da m=p+km = p + k y el segundo da m=pm = p. Como k≥1k \geq 1, no pueden cumplirse las dos. Luego xy2z∉Dxy^2z \notin D, y eso contradice la condición 1. ∎

Aquí también hay cadenas que no sirven. Con s=02ps = \mathtt{0}^{2p}, que está en DD con w=0pw = \mathtt{0}^p, el adversario elige y=00y = \mathtt{00} y todas las cadenas bombeadas son 02p−2+2i\mathtt{0}^{2p-2+2i}: una cantidad par de ceros, que siempre está en DD. Los unos de nuestra cadena son marcas que dicen dónde termina cada mitad, y por eso el adversario no puede desordenarla sin que se note.

En la práctica. En la semana 3 quedó pendiente por qué las referencias hacia atrás no son regulares. Muchas herramientas aceptan patrones como ^(.*)\1$, donde \1 significa “aquí, otra vez, el mismo texto que coincidió con el primer paréntesis”. Sobre el alfabeto {0,1}\{\mathtt{0}, \mathtt{1}\}, ese patrón describe exactamente el lenguaje DD. Acabamos de demostrar que ningún DFA lo reconoce, así que un motor que acepte \1 no puede funcionar simulando un autómata finito: tiene que usar backtracking, con el costo que vieron en la semana 3.

El lenguaje de los cuadrados

Teorema. C={ 0n2:n≥0 }C = \{\, \mathtt{0}^{n^2} : n \geq 0 \,\} no es regular.

El alfabeto es {0}\{\mathtt{0}\}: las cadenas son ε\varepsilon, 0\mathtt{0}, 0000\mathtt{0000}, 09\mathtt{0}^9, 016\mathtt{0}^{16}, … Con un solo símbolo no hay orden que desordenar. Lo único que el bombeo cambia es la longitud, y el argumento es aritmético: los cuadrados están cada vez más separados, y bombear suma poco.

Demostración. Por contradicción, con el lema de bombeo. Supongamos que CC es regular.

Jugada 1. El adversario elige p≥1p \geq 1.

Jugada 2. Elegimos s=0p2s = \mathtt{0}^{p^2}. Está en CC, y ∣s∣=p2≥p|s| = p^2 \geq p porque p≥1p \geq 1.

Jugada 3. El adversario elige s=xyzs = xyz con ∣y∣>0|y| > 0 y ∣xy∣≤p|xy| \leq p. Sea k=∣y∣k = |y|. Entonces 1≤k≤p1 \leq k \leq p, porque ∣y∣≤∣xy∣≤p|y| \leq |xy| \leq p.

Jugada 4. Elegimos i=2i = 2. La cadena xy2zxy^2z tiene un bloque yy más que ss, así que su longitud es p2+kp^2 + k, y

p2  <  p2+k  ≤  p2+p  <  p2+2p+1=(p+1)2.p^2 \;<\; p^2 + k \;\leq\; p^2 + p \;<\; p^2 + 2p + 1 = (p + 1)^2.

La longitud de xy2zxy^2z está estrictamente entre dos cuadrados consecutivos, p2p^2 y (p+1)2(p+1)^2. No es un cuadrado, y xy2z∉Cxy^2z \notin C. Contradicción con la condición 1. ∎

La elección de ss fue otra vez lo que importó. El salto de p2p^2 al cuadrado siguiente es 2p+12p + 1, y el adversario solo puede sumar entre 1 y pp.

Más ceros que unos: bombear hacia abajo

Teorema. G={ 0i1j:i>j≥0 }G = \{\, \mathtt{0}^i\mathtt{1}^j : i > j \geq 0 \,\} no es regular.

Un primer intento. Elegimos s=0p+11ps = \mathtt{0}^{p+1}\mathtt{1}^p, que está en GG, y como siempre yy queda hecha solo de ceros. Si bombeamos con i=2i = 2, sale 0p+1+k1p\mathtt{0}^{p+1+k}\mathtt{1}^p: más ceros todavía. La cadena sigue en GG, y lo mismo con cualquier exponente mayor. Bombear hacia arriba no saca a ninguna cadena de este lenguaje:

$ build/pumping_game mas-ceros-mal 3
L = { 0^i 1^j : i > j }
el adversario elige p = 3
nosotros elegimos s = 0000111, con |s| = 7 y s ∈ L
nuestro exponente: i = 2
divisiones posibles con |xy| ≤ 3 y |y| > 0: 6
  x   y    z       x y^i z
  ε   0    000111  00000111    ∈ L: el adversario resiste
  ε   00   00111   000000111   ∈ L: el adversario resiste
  ε   000  0111    0000000111  ∈ L: el adversario resiste
  0   0    00111   00000111    ∈ L: el adversario resiste
  0   00   0111    000000111   ∈ L: el adversario resiste
  00  0    0111    00000111    ∈ L: el adversario resiste
el adversario tiene 6 divisiones que resisten: con esta jugada no se demuestra nada

Queda un exponente por probar: i=0i = 0, que quita yy.

Demostración. Por contradicción, con el lema de bombeo. Supongamos que GG es regular.

Jugada 1. El adversario elige p≥1p \geq 1.

Jugada 2. Elegimos s=0p+11ps = \mathtt{0}^{p+1}\mathtt{1}^p. Está en GG, porque p+1>pp + 1 > p, y ∣s∣=2p+1≥p|s| = 2p + 1 \geq p.

Jugada 3. El adversario elige s=xyzs = xyz con ∣y∣>0|y| > 0 y ∣xy∣≤p|xy| \leq p. Los primeros pp símbolos son ceros, así que y=0ky = \mathtt{0}^k con 1≤k≤p1 \leq k \leq p.

Jugada 4. Elegimos i=0i = 0:

xy0z=xz=0p+1−k1p.xy^0z = xz = \mathtt{0}^{p+1-k}\mathtt{1}^p.

Como k≥1k \geq 1, la cantidad de ceros es p+1−k≤pp + 1 - k \leq p: ya no es mayor que la de unos. Luego xz∉Gxz \notin G, y eso contradice la condición 1, que vale también para i=0i = 0. ∎

$ build/pumping_game mas-ceros 3
L = { 0^i 1^j : i > j }
el adversario elige p = 3
nosotros elegimos s = 0000111, con |s| = 7 y s ∈ L
nuestro exponente: i = 0
divisiones posibles con |xy| ≤ 3 y |y| > 0: 6
  x   y    z       x y^i z
  ε   0    000111  000111   ∉ L
  ε   00   00111   00111    ∉ L
  ε   000  0111    0111     ∉ L
  0   0    00111   000111   ∉ L
  0   00   0111    00111    ∉ L
  00  0    0111    000111   ∉ L
en las 6 divisiones la cadena bombeada sale de L

La cadena se eligió justa: con un solo cero de ventaja, quitar cualquier yy no vacía ya rompe la condición. Con s=02p1ps = \mathtt{0}^{2p}\mathtt{1}^p el argumento falla, porque el adversario elige y=0y = \mathtt{0} y al quitarla quedan 2p−12p - 1 ceros, que siguen siendo más que pp unos cuando p≥2p \geq 2.

Idea clave. El exponente es una elección, y i=0i = 0 es tan legítimo como i=2i = 2. Si el lenguaje pide “al menos tantos” de algo, bombear hacia arriba no lo rompe y hay que bombear hacia abajo. La cadena se elige en el borde de la condición, para que el menor cambio la saque.

Combinar con las propiedades de cierre

A veces el lenguaje es incómodo para el lema, pero se puede transformar en uno que ya sabemos que no es regular. Las propiedades de cierre de las semanas 1 y 2 se usan entonces al revés.

El esquema es este. Queremos demostrar que LL no es regular. Suponemos que lo es. Le aplicamos operaciones bajo las que los lenguajes regulares son cerrados, con otros lenguajes que sí son regulares, y llegamos a un lenguaje que sabemos que no es regular. Como las operaciones conservan la regularidad, eso es una contradicción.

Otra demostración de que EE no es regular. Por contradicción, usando cierre bajo intersección. Supongamos que EE, el lenguaje de las cadenas con tantos ceros como unos, es regular. El lenguaje 0∗1∗\mathtt{0}^*\mathtt{1}^* es regular, porque lo describe una expresión regular. Los lenguajes regulares son cerrados bajo intersección, por la construcción del producto de la semana 1, así que E∩0∗1∗E \cap \mathtt{0}^*\mathtt{1}^* sería regular. Pero

E∩0∗1∗={ 0n1n:n≥0 }=B,E \cap \mathtt{0}^*\mathtt{1}^* = \{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} = B,

porque una cadena de la forma 0a1b\mathtt{0}^a\mathtt{1}^b tiene tantos ceros como unos exactamente cuando a=ba = b. Y BB no es regular. Contradicción. ∎

La intersección hizo de filtro: de todas las cadenas de EE se quedó con las ordenadas, y ahí el problema difícil queda a la vista.

Con el complemento. El lenguaje de las cadenas binarias con distinta cantidad de ceros y unos tampoco es regular. Usar el lema de bombeo directamente es incómodo: hay que encontrar una cadena que, bombeada, caiga justo en la igualdad. Con cierre es una línea: su complemento es EE, y si un lenguaje es regular su complemento también lo es. Como EE no es regular, este tampoco.

Error común. Usar el cierre en la dirección que no vale. De ”LL contiene a un lenguaje no regular” no se concluye nada: Σ∗\Sigma^* contiene a todos los lenguajes y es regular. De ”LL está contenido en un lenguaje no regular” tampoco: ∅\emptyset está contenido en todos. Y de ”L1∩L2L_1 \cap L_2 es regular” no sale que L1L_1 lo sea. Lo que dicen las propiedades de cierre es una sola cosa: si los datos son regulares, el resultado es regular. Para usarlas en una demostración de imposibilidad, el lenguaje sospechoso tiene que estar entre los datos, y todos los demás datos tienen que ser regulares.

Lo que el lema no dice

No sirve para demostrar que un lenguaje es regular. El lema es una implicación en un solo sentido: si AA es regular, entonces AA tiene la propiedad de bombeo. Lo que usamos toda la sesión es su contrarrecíproca: si no tiene la propiedad, no es regular. La implicación en el otro sentido, “si tiene la propiedad, es regular”, es otra afirmación, y es falsa.

Un lenguaje que lo muestra, sobre el alfabeto {a,b,c}\{\mathtt{a}, \mathtt{b}, \mathtt{c}\}:

T={ aibjck:i,j,k≥0, y si i=1 entonces j=k }T = \{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i, j, k \geq 0, \text{ y si } i = 1 \text{ entonces } j = k \,\}

Si la cadena empieza con exactamente una a\mathtt{a}, se le exige tener tantas b\mathtt{b} como c\mathtt{c}. Si empieza con cero, dos o más, no se le exige nada.

TT tiene la propiedad de bombeo, con p=2p = 2. Sea s∈Ts \in T con ∣s∣≥2|s| \geq 2. Damos una división con x=εx = \varepsilon, según con cuántas a\mathtt{a} empieza ss:

  • Ninguna. yy es el primer símbolo de ss, una b\mathtt{b} o una c\mathtt{c}. Bombearla cambia cuántas hay de esa letra, la cadena sigue siendo de la forma bjck\mathtt{b}^j\mathtt{c}^k, y con i=0i = 0 no se le exige nada.
  • Exactamente una. y=ay = \mathtt{a}. Las cadenas bombeadas son atbjcj\mathtt{a}^t\mathtt{b}^j\mathtt{c}^j con t≥0t \geq 0: están en TT para t=1t = 1 porque j=kj = k, y para los demás tt porque no se exige nada.
  • Exactamente dos. y=aay = \mathtt{aa}. Las cadenas bombeadas empiezan con 0,2,4,…0, 2, 4, \ldots letras a\mathtt{a}: nunca con exactamente una.
  • Tres o más. y=ay = \mathtt{a}. Las cadenas bombeadas empiezan con al menos dos letras a\mathtt{a}.

En los cuatro casos ∣y∣>0|y| > 0, ∣xy∣≤2|xy| \leq 2 y todas las cadenas xytzxy^tz están en TT. El adversario gana siempre: con el lema de bombeo no se puede demostrar que TT no es regular.

Y TT no es regular. Si lo fuera, también lo sería T∩ab∗c∗T \cap \mathtt{a}\mathtt{b}^*\mathtt{c}^*, por cierre bajo intersección. Ese lenguaje es { abncn:n≥0 }\{\, \mathtt{a}\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\}, y que no es regular se demuestra igual que para BB: con s=abpcps = \mathtt{a}\mathtt{b}^p\mathtt{c}^p, la condición ∣xy∣≤p|xy| \leq p deja a yy dentro de abp−1\mathtt{a}\mathtt{b}^{p-1}. Si yy contiene la a\mathtt{a}, con i=0i = 0 la cadena ya no empieza con a\mathtt{a} y sale del lenguaje. Si no, y=bky = \mathtt{b}^k con k≥1k \geq 1, y con i=2i = 2 hay más letras b\mathtt{b} que c\mathtt{c}.

Así que el lema de bombeo es una herramienta incompleta: detecta muchos lenguajes no regulares, pero no todos. La herramienta de la sesión B no tiene ese defecto: caracteriza a los lenguajes regulares exactamente, y con ella TT sale en dos líneas.

Error común. “Encontré una división que se puede bombear, así que el lenguaje es regular.” No: ni siquiera mostrar que toda cadena larga se puede bombear alcanza, como acaba de verse con TT. Para demostrar que un lenguaje es regular se da un DFA, un NFA o una expresión regular, o se lo arma con operaciones de cierre a partir de lenguajes regulares.

Un resumen de qué herramienta sirve para qué:

Quiero demostrar que LL… Sirve No sirve
es regular Un DFA, un NFA, una expresión regular; cierre a partir de lenguajes regulares El lema de bombeo
no es regular El lema de bombeo; cierre hasta un lenguaje que no es regular; cadenas distinguibles “No se me ocurre un DFA”

Cadenas distinguibles

La segunda herramienta parte de la misma limitación, mirada de otro modo. El lema de bombeo sigue una cadena larga y encuentra un estado que se repite. Ahora vamos a comparar dos cadenas y preguntar si un autómata puede permitirse confundirlas.

Piensen otra vez en B={ 0n1n }B = \{\, \mathtt{0}^n\mathtt{1}^n \,\} y en un DFA que ya leyó 000\mathtt{000}. Para responder bien más adelante tiene que recordar que fueron tres ceros y no cinco: si después llegan tres unos debe aceptar, y si hubiera leído 00000\mathtt{00000} y llegan esos mismos tres unos debe rechazar. Las cadenas 000\mathtt{000} y 00000\mathtt{00000} tienen futuros distintos, y un autómata que las confunda se equivoca en alguno de los dos.

Definición. Sea LL un lenguaje sobre Σ\Sigma. Dos cadenas x,y∈Σ∗x, y \in \Sigma^* son distinguibles (distinguishable) respecto de LL si existe una cadena z∈Σ∗z \in \Sigma^* tal que exactamente una de las cadenas xzxz e yzyz está en LL. De esa zz se dice que es un sufijo que distingue a xx de yy. Si no existe ninguna, xx e yy son indistinguibles respecto de LL, y se escribe x≡Lyx \equiv_L y:

x≡Lysi y solo sipara toda z∈Σ∗:  xz∈L  ⟺  yz∈L.x \equiv_L y \quad\text{si y solo si}\quad \text{para toda } z \in \Sigma^*: \; xz \in L \iff yz \in L.

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

  • Siempre es respecto de un lenguaje. Las mismas dos cadenas pueden ser distinguibles para un lenguaje e indistinguibles para otro.
  • xx e yy no tienen que estar en LL. Lo que se compara es lo que pasa después de ellas. El sufijo zz es el mismo para las dos.
  • zz puede ser ε\varepsilon. Entonces la condición dice que exactamente una de xx, yy está en LL: una cadena de LL y una de fuera de LL son siempre distinguibles.

Algunos ejemplos, respecto de BB:

  • 000\mathtt{000} y 00000\mathtt{00000} son distinguibles: con z=111z = \mathtt{111}, 000111∈B\mathtt{000111} \in B y 00000111∉B\mathtt{00000111} \notin B.
  • 01\mathtt{01} y 0011\mathtt{0011} son indistinguibles. Las dos están en BB, así que z=εz = \varepsilon no las separa. Y con cualquier zz no vacía, ni 01z\mathtt{01}z ni 0011z\mathtt{0011}z están en BB: si zz empieza con 0\mathtt{0} hay un cero después de un uno, y si empieza con 1\mathtt{1} sobran unos.
  • 1\mathtt{1} y 10\mathtt{10} son indistinguibles: ninguna cadena que empiece con 1\mathtt{1} está en BB, así que 1z\mathtt{1}z y 10z\mathtt{10}z quedan fuera para toda zz.

Cuando el lenguaje es regular y tenemos un DFA suyo, la pregunta se puede responder con un programa. El más directo hace lo que dice la definición: prueba sufijos, del más corto al más largo. Con el autómata de 8 estados de la sección siguiente, que reconoce “el tercer símbolo desde el final es 1\mathtt{1}”:

$ build/distinguish machines/last_3.dfa 011 001
x = 011 llega a 011, y = 001 llega a 001
sufijos probados, del más corto al más largo: 2
z = 0 las distingue: xz = 0110 se acepta, yz = 0010 se rechaza

El sufijo ε\varepsilon no las separa, porque ninguna de las dos tiene un 1\mathtt{1} en la tercera posición desde el final. Con z=0z = \mathtt{0}, lo que queda en esa posición es el segundo símbolo de cada una, y ahí difieren.

Dos cadenas distinguibles no pueden terminar en el mismo estado

Lema (de los estados distintos). Sea M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) un DFA que reconoce LL. Si xx e yy son distinguibles respecto de LL, entonces δ∗(q0,x)≠δ∗(q0,y)\delta^*(q_0, x) \neq \delta^*(q_0, y).

Demostración. Por la contrarrecíproca: si xx e yy llegan al mismo estado, son indistinguibles. Supongamos δ∗(q0,x)=δ∗(q0,y)\delta^*(q_0, x) = \delta^*(q_0, y), y sea zz una cadena cualquiera. Por el lema de la concatenación,

δ∗(q0,xz)=δ∗(δ∗(q0,x),z)=δ∗(δ∗(q0,y),z)=δ∗(q0,yz).\delta^*(q_0, xz) = \delta^*(\delta^*(q_0, x), z) = \delta^*(\delta^*(q_0, y), z) = \delta^*(q_0, yz).

Las cadenas xzxz e yzyz terminan en el mismo estado, así que MM acepta las dos o rechaza las dos. Como L(M)=LL(M) = L, eso dice que xz∈L  ⟺  yz∈Lxz \in L \iff yz \in L. Vale para toda zz: ninguna distingue a xx de yy. ∎

Es la observación que cerraba la sección de δ∗\delta^* en la semana 1: después de leer xx, el estado es todo lo que la máquina recuerda. Si dos cadenas tienen futuros distintos, la máquina está obligada a recordar cuál de las dos leyó.

Teorema (cota inferior de estados). Sea LL un lenguaje y sea SS un conjunto de kk cadenas distinguibles dos a dos respecto de LL. Entonces todo DFA que reconoce LL tiene al menos kk estados.

Demostración. Por contradicción, con el principio del palomar. Supongamos que un DFA MM con menos de kk estados reconoce LL. Cada una de las kk cadenas de SS lleva a MM a algún estado, y hay menos estados que cadenas: dos cadenas distintas de SS, digamos xx e yy, terminan en el mismo. Por el lema de los estados distintos, xx e yy no son distinguibles. Pero todas las cadenas de SS lo son dos a dos. Contradicción. ∎

“Distinguibles dos a dos” quiere decir que cada par de cadenas distintas de SS tiene un sufijo que lo distingue. El sufijo puede ser distinto para cada par. En inglés, un conjunto así se llama fooling set, y es el nombre con el que aparece en las notas de Erickson.

Corolario. Si hay un conjunto infinito de cadenas distinguibles dos a dos respecto de LL, entonces LL no es regular.

Demostración. Por contradicción. Si LL fuera regular, lo reconocería un DFA con algún número nn de estados. Del conjunto infinito tomamos n+1n + 1 cadenas. Son distinguibles dos a dos, así que por el teorema todo DFA de LL tiene al menos n+1n + 1 estados. Contradicción. ∎

0ⁿ1ⁿ otra vez, en tres líneas

Teorema. B={ 0n1n:n≥0 }B = \{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} no es regular.

Demostración. Con cadenas distinguibles. Sea S={ 0i:i≥0 }S = \{\, \mathtt{0}^i : i \geq 0 \,\}, que es infinito. Dos cadenas distintas de SS son 0i\mathtt{0}^i y 0j\mathtt{0}^j con i≠ji \neq j. El sufijo z=1iz = \mathtt{1}^i las distingue: 0i1i∈B\mathtt{0}^i\mathtt{1}^i \in B y 0j1i∉B\mathtt{0}^j\mathtt{1}^i \notin B. Por el corolario, BB no es regular. ∎

No hubo adversario, ni división, ni casos. Y es el argumento informal del final de la semana 1, ahora completo: “un DFA con nn estados no puede distinguir n+1n + 1 cantidades” es el teorema de la cota inferior aplicado a 00,01,…,0n\mathtt{0}^0, \mathtt{0}^1, \ldots, \mathtt{0}^n.

Los otros lenguajes de la sesión A salen igual de rápido.

  • Más ceros que unos, GG. Con S={ 0i:i≥0 }S = \{\, \mathtt{0}^i : i \geq 0 \,\}: si i<ji < j, el sufijo z=1iz = \mathtt{1}^i da 0i1i∉G\mathtt{0}^i\mathtt{1}^i \notin G y 0j1i∈G\mathtt{0}^j\mathtt{1}^i \in G.
  • Los cuadrados, CC. Con S={ 0i2:i≥0 }S = \{\, \mathtt{0}^{i^2} : i \geq 0 \,\}: si i<ji < j, el sufijo z=02i+1z = \mathtt{0}^{2i+1} lleva la primera a longitud i2+2i+1=(i+1)2i^2 + 2i + 1 = (i+1)^2, que es un cuadrado, y la segunda a j2+2i+1j^2 + 2i + 1, que está estrictamente entre j2j^2 y (j+1)2=j2+2j+1(j+1)^2 = j^2 + 2j + 1, y no lo es.
  • El lenguaje TT, el que resistía al lema de bombeo. Con S={ abi:i≥0 }S = \{\, \mathtt{a}\mathtt{b}^i : i \geq 0 \,\}: si i≠ji \neq j, el sufijo z=ciz = \mathtt{c}^i da abici∈T\mathtt{a}\mathtt{b}^i\mathtt{c}^i \in T y abjci∉T\mathtt{a}\mathtt{b}^j\mathtt{c}^i \notin T.

Idea clave. Para demostrar que LL no es regular con cadenas distinguibles hay que dar dos cosas: un conjunto infinito de cadenas, y para cada par de ellas un sufijo que deja a una dentro de LL y a la otra fuera. Las cadenas del conjunto son “lo que el autómata tendría que recordar”.

Error común. Dar un conjunto infinito de cadenas y distinguir solo algunos pares, por ejemplo cada cadena de la siguiente. Hace falta un sufijo para todo par i≠ji \neq j. El otro error frecuente es usar un sufijo distinto para cada cadena del par: zz es una sola, y se le pega a las dos.

La deuda de la semana 2: 2ᵏ estados

En la semana 2 vimos el lenguaje

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

Una cadena de longitud menor que kk no tiene kk-ésimo símbolo desde el final, y no está en LkL_k. Un NFA lo reconoce con k+1k + 1 estados: adivina cuál es el 1\mathtt{1} que importa y cuenta los k−1k - 1 símbolos que faltan. La construcción de subconjuntos dio un DFA con 2k2^k estados, y quedó sin demostrar que no se puede con menos. La intuición era que un DFA tiene que recordar los últimos kk símbolos, porque cualquiera de ellos puede terminar siendo el que decide. Ahora esa intuición es una demostración.

Teorema. Todo DFA que reconoce LkL_k tiene al menos 2k2^k estados.

Demostración. Con cadenas distinguibles. Sea SS el conjunto de todas las cadenas binarias de longitud kk. Son 2k2^k. Veamos que son distinguibles dos a dos respecto de LkL_k.

Sean x≠yx \neq y dos cadenas de longitud kk. Como son distintas, difieren en alguna posición: hay un ii, con 1≤i≤k1 \leq i \leq k, tal que el símbolo ii de xx y el símbolo ii de yy son distintos. Uno es 1\mathtt{1} y el otro 0\mathtt{0}. Digamos que el de xx es el 1\mathtt{1}; si no, se intercambian los nombres.

Tomamos z=0i−1z = \mathtt{0}^{i-1}. La cadena xzxz tiene longitud k+i−1k + i - 1. Su kk-ésimo símbolo desde el final está en la posición

(k+i−1)−k+1=i(k + i - 1) - k + 1 = i

contando desde el principio, y esa posición cae dentro de xx: es el símbolo ii de xx, un 1\mathtt{1}. Luego xz∈Lkxz \in L_k. El mismo cálculo con yzyz da el símbolo ii de yy, un 0\mathtt{0}: yz∉Lkyz \notin L_k. El sufijo zz distingue a xx de yy.

Por el teorema de la cota inferior, todo DFA de LkL_k tiene al menos ∣S∣=2k|S| = 2^k estados. ∎

El sufijo 0i−1\mathtt{0}^{i-1} empuja la posición ii hasta que queda justo a distancia kk del final. Con k=3k = 3, las cadenas 011\mathtt{011} y 001\mathtt{001} difieren en la posición 2, y el sufijo es 01\mathtt{0}^1: es lo que encontró distinguish en la sección anterior.

Figura en dos partes. A la izquierda, dos cadenas en celdas con las posiciones 1, 2 y 3 numeradas: x = 011 e y = 001. La posición 2, en la que difieren, está resaltada. A cada una se le agrega el sufijo z = 0, y un corchete marca los tres últimos símbolos de la cadena resultante: el tercero desde el final de xz = 0110 es el 1 de la posición 2 de x, y el tercero desde el final de yz = 0010 es el 0 de la posición 2 de y. A la derecha, lo mismo en el DFA de 8 estados: x llega al estado 011, que con 0 pasa a 110, de aceptación, así que 0110 está en L₃; y llega al estado 001, que con 0 pasa a 010, que no es de aceptación, así que 0010 no está en L₃. Al pie: un DFA que llevara 011 y 001 al mismo estado respondería igual a 0110 y a 0010, y se equivocaría en unaFigura en dos partes. A la izquierda, dos cadenas en celdas con las posiciones 1, 2 y 3 numeradas: x = 011 e y = 001. La posición 2, en la que difieren, está resaltada. A cada una se le agrega el sufijo z = 0, y un corchete marca los tres últimos símbolos de la cadena resultante: el tercero desde el final de xz = 0110 es el 1 de la posición 2 de x, y el tercero desde el final de yz = 0010 es el 0 de la posición 2 de y. A la derecha, lo mismo en el DFA de 8 estados: x llega al estado 011, que con 0 pasa a 110, de aceptación, así que 0110 está en L₃; y llega al estado 001, que con 0 pasa a 010, que no es de aceptación, así que 0010 no está en L₃. Al pie: un DFA que llevara 011 y 001 al mismo estado respondería igual a 0110 y a 0010, y se equivocaría en una
El sufijo de i − 1 ceros deja la posición en la que difieren justo en el tercer lugar desde el final. Las dos cadenas tienen futuros distintos, y ningún DFA puede llevarlas al mismo estado.

La cota se alcanza. El autómata que recuerda los últimos kk símbolos tiene exactamente 2k2^k estados: su estado es una cadena de kk bits, al leer un símbolo olvida el más antiguo y agrega el nuevo al final, y acepta si el más antiguo es 1\mathtt{1}. Mientras no ha leído kk símbolos, cuenta los que faltan como 0\mathtt{0}, de modo que el estado inicial es 0k\mathtt{0}^k y una cadena corta se rechaza. Es el autómata de la construcción de subconjuntos de la semana 2 con otros nombres para los estados. En esta carpeta lo escribe directamente el programa kth_from_end, sin pasar por el NFA, y machines/last_3.dfa es su salida para k=3k = 3:

$ build/show_dfa machines/last_3.dfa
Q  = {000, 001, 010, 011, 100, 101, 110, 111}
Σ  = {0, 1}
q0 = 000
F  = {100, 101, 110, 111}

     δ    0    1
->   000  000  001
     001  010  011
     010  100  101
     011  110  111
   * 100  000  001
   * 101  010  011
   * 110  100  101
   * 111  110  111

estados alcanzables desde 000: 8 de 8

Con el autómata en la mano, el programa fooling_set comprueba un conjunto distinguible: recibe las cadenas y busca, para cada par, el sufijo más corto que lo distingue.

$ build/fooling_set machines/last_3.dfa 000 001 010 011 100 101 110 111
sufijo más corto que distingue a cada par (fila, columna):
       001  010  011  100  101  110  111
  000  00   0    0    ε    ε    ε    ε
  001  .    0    0    ε    ε    ε    ε
  010  .    .    00   ε    ε    ε    ε
  011  .    .    .    ε    ε    ε    ε
  100  .    .    .    .    00   0    0
  101  .    .    .    .    .    0    0
  110  .    .    .    .    .    .    00
8 cadenas distinguibles dos a dos: todo DFA de este lenguaje tiene al menos 8 estados (este tiene 8)

La tabla tiene un sufijo en cada casilla: los 28 pares son distinguibles. Coincide con la demostración. Los pares que difieren ya en la primera posición se distinguen con ε\varepsilon; los que coinciden en la primera y difieren en la segunda, con 0\mathtt{0}; y los que solo difieren en la tercera, con 00\mathtt{00}.

Entonces, para LkL_k, el DFA más pequeño tiene exactamente 2k2^k estados, y el NFA tiene k+1k + 1. La construcción de subconjuntos no desperdicia nada en este ejemplo: el salto exponencial es inevitable.

En la práctica. Este es el motivo por el que las herramientas que buscan con expresiones regulares no siempre convierten el patrón en un DFA completo antes de empezar. Un patrón corto como “una a seguida de exactamente 20 caracteres cualesquiera, al final de la línea” tiene un NFA de 22 estados y un DFA mínimo de más de un millón. Las alternativas son simular el NFA directamente, como en el laboratorio de la semana 3, o construir los estados del DFA a medida que la entrada los necesita y guardar solo los que aparecen.

El teorema de Myhill-Nerode

El teorema de la cota inferior dice que un conjunto de kk cadenas distinguibles obliga a tener kk estados. La pregunta natural es si esa cota es siempre la mejor: si lo máximo que se puede encontrar son kk cadenas distinguibles dos a dos, ¿alcanza un DFA con kk estados? La respuesta es sí, y es el teorema que cierra la teoría de los lenguajes regulares.

Las clases de equivalencia

La relación ≡L\equiv_L entre cadenas, “ser indistinguibles respecto de LL”, es una relación de equivalencia:

  • Reflexiva: x≡Lxx \equiv_L x, porque xz∈L  ⟺  xz∈Lxz \in L \iff xz \in L.
  • Simétrica: si x≡Lyx \equiv_L y entonces y≡Lxy \equiv_L x, porque la condición trata igual a las dos.
  • Transitiva: si x≡Lyx \equiv_L y e y≡Lwy \equiv_L w, entonces para toda zz se tiene xz∈L  ⟺  yz∈L  ⟺  wz∈Lxz \in L \iff yz \in L \iff wz \in L, así que x≡Lwx \equiv_L w.

Como en Matemática Discreta, una relación de equivalencia parte al conjunto en clases de equivalencia (equivalence classes): la clase de xx, que se escribe [x][x], es el conjunto de todas las cadenas indistinguibles de xx. Cada cadena de Σ∗\Sigma^* está en exactamente una clase. Dos cadenas de la misma clase son indistinguibles, y dos cadenas de clases distintas son distinguibles.

Dos propiedades de las clases, que salen de la definición y se usan enseguida.

Lema (de las clases). Si x≡Lyx \equiv_L y, entonces:

  • (a) x∈L  ⟺  y∈Lx \in L \iff y \in L;
  • (b) xa≡Lyaxa \equiv_L ya para todo símbolo a∈Σa \in \Sigma.

Demostración. Las dos por aplicación directa de la definición, eligiendo el sufijo. Para (a), se toma z=εz = \varepsilon en la definición de x≡Lyx \equiv_L y. Para (b), sea zz una cadena cualquiera. Hay que ver que (xa)z∈L  ⟺  (ya)z∈L(xa)z \in L \iff (ya)z \in L. Pero (xa)z=x(az)(xa)z = x(az) e (ya)z=y(az)(ya)z = y(az), y la definición de x≡Lyx \equiv_L y con el sufijo azaz dice exactamente x(az)∈L  ⟺  y(az)∈Lx(az) \in L \iff y(az) \in L. ∎

La parte (a) dice que cada clase está entera dentro de LL o entera fuera. La parte (b) dice que si a dos cadenas de una misma clase se les agrega el mismo símbolo, siguen en una misma clase. Leídas juntas, dicen que las clases se comportan como los estados de un DFA.

El programa classes calcula las clases del lenguaje de un DFA. Con el autómata de 7 estados que la semana 1 descartó por recordar de más, el que guarda los dos últimos símbolos para decidir si la cadena termina en 01\mathtt{01}:

$ build/classes machines/ends_01_seven.dfa 3
clases de equivalencia: 3
  [ε] (fuera de L): ε 1 11 011 111
  [0] (fuera de L): 0 00 10 000 010 100 110
  [01] (en L): 01 001 101
el autómata de las clases:
states: [ε] [0] [01]
alphabet: 0 1
start: [ε]
accept: [01]
delta:
[ε] 0 [0]
[ε] 1 [ε]
[0] 0 [0]
[0] 1 [01]
[01] 0 [0]
[01] 1 [ε]

Hay tres clases. En cada línea está su representante, entre corchetes, y las cadenas de longitud a lo sumo 3 que caen en ella. La clase [ε][\varepsilon] tiene las cadenas que no terminan en 0\mathtt{0} ni en 01\mathtt{01}; la clase [0][\mathtt{0}], las que terminan en 0\mathtt{0}; la clase [01][\mathtt{01}], las que terminan en 01\mathtt{01}. Son exactamente los tres hechos que anotamos al diseñar el autómata de 3 estados en la semana 1. No es casualidad, y el teorema dice por qué.

Para un lenguaje que no es regular, las clases no se acaban. Respecto de BB, las cadenas 00,01,02,…\mathtt{0}^0, \mathtt{0}^1, \mathtt{0}^2, \ldots están cada una en una clase distinta.

El teorema

Teorema (Myhill-Nerode). Sea LL un lenguaje sobre Σ\Sigma.

  1. Si un DFA con nn estados reconoce LL, entonces ≡L\equiv_L tiene a lo sumo nn clases de equivalencia.
  2. Si ≡L\equiv_L tiene un número finito kk de clases de equivalencia, entonces hay un DFA con exactamente kk estados que reconoce LL.

En consecuencia, LL es regular si y solo si ≡L\equiv_L tiene un número finito de clases, y ese número es el de estados del DFA más pequeño que reconoce LL.

Demostración de 1. Por contradicción, con el teorema de la cota inferior. Supongamos que un DFA con nn estados reconoce LL y que ≡L\equiv_L tiene más de nn clases. Tomamos una cadena de cada una de n+1n + 1 clases distintas. Dos cadenas de clases distintas son distinguibles, así que tenemos n+1n + 1 cadenas distinguibles dos a dos, y por el teorema de la cota inferior todo DFA de LL tiene al menos n+1n + 1 estados. Contradicción. ∎

Demostración de 2. Por construcción. Supongamos que ≡L\equiv_L tiene kk clases.

Qué se construye. El DFA ML=(Q,Σ,δ,q0,F)M_L = (Q, \Sigma, \delta, q_0, F) cuyos estados son las clases:

Q={ [x]:x∈Σ∗ }las k clasesδ([x],a)=[xa]para cada clase y cada sıˊmbolo aq0=[ε]F={ [x]:x∈L }\begin{aligned} Q &= \{\, [x] : x \in \Sigma^* \,\} && \text{las } k \text{ clases} \\ \delta([x], a) &= [xa] && \text{para cada clase y cada símbolo } a \\ q_0 &= [\varepsilon] \\ F &= \{\, [x] : x \in L \,\} \end{aligned}

Está bien definido. Una clase tiene muchos nombres: si x≡Lyx \equiv_L y, entonces [x][x] y [y][y] son el mismo estado. La definición de δ\delta y la de FF usan un representante, y hay que comprobar que el resultado no depende de cuál se use. Para δ\delta: si [x]=[y][x] = [y], por la parte (b) del lema de las clases xa≡Lyaxa \equiv_L ya, es decir, [xa]=[ya][xa] = [ya]. Para FF: si [x]=[y][x] = [y], por la parte (a), x∈L  ⟺  y∈Lx \in L \iff y \in L. Y QQ es finito porque hay kk clases.

Por qué reconoce LL. Primero, una afirmación sobre dónde termina cada cadena: para toda w∈Σ∗w \in \Sigma^*,

δ∗([ε],w)=[w].\delta^*([\varepsilon], w) = [w].

Por inducción sobre ∣w∣|w|. Caso base: δ∗([ε],ε)=[ε]\delta^*([\varepsilon], \varepsilon) = [\varepsilon] por la definición de δ∗\delta^*. Paso inductivo: si w=uaw = ua y la afirmación vale para uu,

δ∗([ε],ua)=δ(δ∗([ε],u),a)=δ([u],a)=[ua].\delta^*([\varepsilon], ua) = \delta(\delta^*([\varepsilon], u), a) = \delta([u], a) = [ua].

Con eso, para toda cadena ww:

ML acepta w  ⟺  δ∗([ε],w)∈Fdefinicioˊn de aceptar  ⟺  [w]∈Fla afirmacioˊn  ⟺  w∈Ldefinicioˊn de F, que no depende del representante\begin{aligned} M_L \text{ acepta } w &\iff \delta^*([\varepsilon], w) \in F && \text{definición de aceptar} \\ &\iff [w] \in F && \text{la afirmación} \\ &\iff w \in L && \text{definición de } F \text{, que no depende del representante} \end{aligned}

Luego L(ML)=LL(M_L) = L, y MLM_L tiene kk estados. ∎

La consecuencia. Si LL es regular, lo reconoce algún DFA, y por la parte 1 hay finitas clases. Si hay finitas clases, por la parte 2 es regular. Y si hay kk clases: la parte 2 da un DFA con kk estados, y la parte 1 dice que ninguno tiene menos, porque un DFA con nn estados obliga a que k≤nk \leq n. ∎

La afirmación δ∗([ε],w)=[w]\delta^*([\varepsilon], w) = [w] dice qué es el autómata MLM_L: la máquina que después de leer ww recuerda la clase de ww, y nada más. Es lo mínimo que se puede recordar, porque dos cadenas de clases distintas tienen que distinguirse, y es suficiente, porque la clase de ww ya dice si w∈Lw \in L y a qué clase pasa con cada símbolo. La salida de classes de arriba termina con ese autómata, escrito en formato .dfa: sus tres estados son [ε], [0] y [01].

Idea clave. Las clases de equivalencia de ≡L\equiv_L son los estados que cualquier autómata de LL necesita. El lenguaje, y no quien lo diseña, decide cuántos estados hacen falta. Si son infinitas, el lenguaje no es regular.

A diferencia del lema de bombeo, este teorema vale en las dos direcciones. Sirve para demostrar que un lenguaje no es regular, mostrando infinitas clases, y también que sí lo es, mostrando que son finitas. Y en este segundo caso da el número exacto de estados.

Minimizar un DFA

El teorema de Myhill-Nerode dice que existe un DFA con el menor número posible de estados, pero lo construye a partir de las clases de ≡L\equiv_L, que son conjuntos infinitos de cadenas. En la práctica no se parte del lenguaje, sino de un DFA que ya lo reconoce y que puede tener estados de más: el que salió de una construcción de subconjuntos, de un producto o de un diseño poco cuidadoso. Minimizarlo es encontrar el DFA más pequeño que reconoce el mismo lenguaje.

Qué estados sobran

Hay dos maneras de que un estado sobre.

Estados inalcanzables. Si ninguna cadena lleva de q0q_0 a un estado, ninguna ejecución pasa por él, y se puede borrar sin cambiar el lenguaje. Los vimos en la semana 1, en la construcción del producto. Se encuentran con un recorrido del grafo de transiciones desde q0q_0.

Estados equivalentes. Dos estados pueden ser alcanzables los dos y, aun así, hacer exactamente lo mismo de ahí en adelante. Es la idea de las cadenas indistinguibles, ahora para estados.

Definición. Sea M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) un DFA. Un sufijo zz distingue a los estados pp y qq si exactamente uno de δ∗(p,z)\delta^*(p, z) y δ∗(q,z)\delta^*(q, z) está en FF. Dos estados son equivalentes, y se escribe p∼qp \sim q, si ningún sufijo los distingue:

p∼qsi y solo sipara toda z∈Σ∗:  δ∗(p,z)∈F  ⟺  δ∗(q,z)∈F.p \sim q \quad\text{si y solo si}\quad \text{para toda } z \in \Sigma^*: \; \delta^*(p, z) \in F \iff \delta^*(q, z) \in F.

Si p∼qp \sim q, da lo mismo estar en uno que en otro: desde los dos se aceptan exactamente las mismas continuaciones. Uno de los dos sobra, y se pueden fusionar en un solo estado.

Las dos nociones de esta sesión son la misma, vista desde las cadenas o desde los estados. Si xx lleva a pp e yy lleva a qq, entonces xz∈L(M)xz \in L(M) exactamente cuando δ∗(p,z)∈F\delta^*(p, z) \in F, por el lema de la concatenación, y lo mismo con yy y qq. Luego:

x≡L(M)ysi y solo siδ∗(q0,x)∼δ∗(q0,y).x \equiv_{L(M)} y \quad\text{si y solo si}\quad \delta^*(q_0, x) \sim \delta^*(q_0, y).

El autómata que usaremos de ejemplo está en machines/contains_1001.dfa. Reconoce las cadenas binarias que contienen 1001\mathtt{1001}, y está escrito con descuido:

$ build/show_dfa machines/contains_1001.dfa
Q  = {q0, q1, q2, q3, q4, q5, q6, q7}
Σ  = {0, 1}
q0 = q0
F  = {q5, q6, q7}

     δ   0   1
->   q0  q4  q1
     q1  q2  q1
     q2  q3  q1
     q3  q4  q5
     q4  q4  q1
   * q5  q6  q5
   * q6  q6  q5
   * q7  q3  q7

estados alcanzables desde q0: 7 de 8
Estado Lo que quiso decir quien lo escribió
q0q_0 Todavía no se leyó nada
q4q_4 Ya se leyó algo, y no hay ningún avance hacia 1001\mathtt{1001}
q1q_1 Lo leído termina en 1\mathtt{1}
q2q_2 Lo leído termina en 10\mathtt{10}
q3q_3 Lo leído termina en 100\mathtt{100}
q5q_5 Ya apareció 1001\mathtt{1001}, y lo último fue un 1\mathtt{1}
q6q_6 Ya apareció 1001\mathtt{1001}, y lo último fue un 0\mathtt{0}
q7q_7 Quedó de una versión anterior

La última línea de la salida dice que hay un estado inalcanzable. Es q7q_7: ninguna transición de los otros estados llega a él. Y a simple vista hay dos parejas sospechosas. Distinguir “no se leyó nada” de “no hay avance” no sirve para nada, y una vez que 1001\mathtt{1001} apareció, da igual cuál fue el último símbolo. El programa distinguish lo confirma para la primera pareja. La cadena ε\varepsilon llega a q0q_0 y la cadena 0\mathtt{0} llega a q4q_4:

$ build/distinguish machines/contains_1001.dfa '' 0
x = ε llega a q0, y = 0 llega a q4
ningún sufijo de longitud a lo sumo |Q| - 1 = 7 las distingue (255 probados): son indistinguibles

En cambio q0q_0 y q1q_1, a los que llegan ε\varepsilon y 1\mathtt{1}, también “se parecen”: ninguno es de aceptación, y con cualquier símbolo los dos van a un estado que no es de aceptación. No son equivalentes:

$ build/distinguish machines/contains_1001.dfa '' 1
x = ε llega a q0, y = 1 llega a q1
sufijos probados, del más corto al más largo: 9
z = 001 las distingue: xz = 001 se rechaza, yz = 1001 se acepta

Hizo falta un sufijo de tres símbolos para separarlos: 1⋅001\mathtt{1} \cdot \mathtt{001} contiene 1001\mathtt{1001} y ε⋅001\varepsilon \cdot \mathtt{001} no. Cuando el programa responde que dos cadenas son indistinguibles, es porque probó todos los sufijos de longitud a lo sumo ∣Q∣−1|Q| - 1; por qué eso alcanza se ve más abajo, en Por qué funciona.

Error común. Fusionar dos estados porque “se parecen”: ninguno es de aceptación, o sus filas de la tabla son casi iguales, o con un símbolo van al mismo lugar. Dos estados se fusionan solo si ningún sufijo los distingue, y el sufijo que los separa puede ser largo. Si en este ejemplo se fusionaran q0q_0 y q1q_1, el autómata ya no podría responder distinto a 001\mathtt{001} y a 1001\mathtt{1001}. Y al revés: dos estados con filas distintas en la tabla, como q5q_5 y q6q_6, pueden ser equivalentes.

distinguish prueba cadenas, y eso no sirve como algoritmo: hay demasiadas. Hace falta una manera de decidir todos los pares de estados a la vez.

Refinar una partición

La idea es calcular la equivalencia ∼\sim por aproximaciones. Empezamos suponiendo que casi todos los estados son equivalentes, y vamos separando los que se demuestra que no lo son, hasta que no haya más que separar.

Una partición de QQ es una manera de repartir los estados en bloques, de modo que cada estado esté en exactamente un bloque. El algoritmo mantiene una partición con este significado: dos estados en bloques distintos ya se sabe que son distinguibles; dos estados en el mismo bloque todavía no se han podido distinguir.

  1. Quitar los estados inalcanzables.
  2. Partición inicial: dos bloques, FF y Q−FQ - F. Un estado de aceptación y uno que no lo es se distinguen con el sufijo ε\varepsilon. Si FF o Q−FQ - F es vacío, queda un solo bloque.
  3. Una ronda: para cada estado y cada símbolo se mira a qué bloque va a parar. Dos estados siguen juntos si estaban en el mismo bloque y, con cada símbolo, van al mismo bloque. Si con algún símbolo aa van a bloques distintos, se separan: los destinos ya se distinguían con algún sufijo zz, así que ellos se distinguen con azaz.
  4. Repetir la ronda hasta que no separe nada.
  5. Fusionar: el DFA mínimo tiene un estado por bloque.

En pseudocódigo:

algoritmo minimizar(M)
    quitar de M los estados a los que no se llega desde q0
    P ← {F, Q − F}, sin los bloques vacíos
    cambió ← verdadero
    mientras cambió
        para cada estado q
            firma[q] ← (bloque de q en P, bloque de δ(q, a) en P para cada símbolo a)
        fin para
        P' ← los estados agrupados por firma: un bloque por cada firma distinta
        cambió ← P' tiene más bloques que P
        P ← P'
    fin mientras
    devolver el autómata con un estado por bloque de P
fin algoritmo

La firma de un estado junta todo lo que la ronda mira de él. Como incluye el bloque en el que ya estaba, una ronda solo puede partir bloques, nunca juntarlos. Por eso, para saber si la partición cambió, basta comparar cuántos bloques hay.

El autómata que se devuelve, que llamaremos el autómata cociente, se arma así: sus estados son los bloques; desde un bloque, con el símbolo aa, va al bloque de δ(q,a)\delta(q, a), donde qq es cualquier estado del bloque; el estado inicial es el bloque que contiene a q0q_0; y un bloque es de aceptación si sus estados lo son. Cuando el algoritmo termina, da lo mismo qué qq del bloque se use: es justamente la condición de parada.

Este procedimiento se conoce como algoritmo de Moore.

Un ejemplo paso a paso

El programa minimize muestra la partición después de cada ronda. Los bloques llevan letras, y en la tabla de cada ronda se ve a qué bloque va cada estado con cada símbolo. Con el autómata de 1001\mathtt{1001}:

$ build/minimize machines/contains_1001.dfa
estados: 8, alcanzables: 7. Se quitan: q7

P0: 2 bloques
  A = {q0, q1, q2, q3, q4}
  B = {q5, q6}

ronda 1: a qué bloque de P0 va cada estado
  estado  está en  con 0  con 1
  q0      A        A      A
  q1      A        A      A
  q2      A        A      A
  q3      A        A      B      <- se separa
  q4      A        A      A
  q5      B        B      B
  q6      B        B      B
P1: 3 bloques
  A = {q0, q1, q2, q4}
  B = {q3}
  C = {q5, q6}

ronda 2: a qué bloque de P1 va cada estado
  estado  está en  con 0  con 1
  q0      A        A      A
  q1      A        A      A
  q2      A        B      A      <- se separa
  q4      A        A      A
  q3      B        A      C
  q5      C        C      C
  q6      C        C      C
P2: 4 bloques
  A = {q0, q1, q4}
  B = {q2}
  C = {q3}
  D = {q5, q6}

ronda 3: a qué bloque de P2 va cada estado
  estado  está en  con 0  con 1
  q0      A        A      A
  q1      A        B      A      <- se separa
  q4      A        A      A
  q2      B        C      A
  q3      C        A      D
  q5      D        D      D
  q6      D        D      D
P3: 5 bloques
  A = {q0, q4}
  B = {q1}
  C = {q2}
  D = {q3}
  E = {q5, q6}

ronda 4: a qué bloque de P3 va cada estado
  estado  está en  con 0  con 1
  q0      A        A      B
  q4      A        A      B
  q1      B        C      B
  q2      C        D      B
  q3      D        A      E
  q5      E        E      E
  q6      E        E      E
P4 = P3: la partición ya no cambia

DFA mínimo: 5 estados
states: {q0,q4} q1 q2 q3 {q5,q6}
alphabet: 0 1
start: {q0,q4}
accept: {q5,q6}
delta:
{q0,q4} 0 {q0,q4}
{q0,q4} 1 q1
q1 0 q2
q1 1 q1
q2 0 q3
q2 1 q1
q3 0 {q0,q4}
q3 1 {q5,q6}
{q5,q6} 0 {q5,q6}
{q5,q6} 1 {q5,q6}
Animación de la minimización del autómata de 8 estados que reconoce las cadenas que contienen 1001. El diagrama: q₀ es inicial; q₀ va con 0 a q₄ y con 1 a q₁; q₁ tiene un bucle con 1 y va con 0 a q₂; q₂ va con 0 a q₃ y con 1 a q₁; q₃ va con 0 a q₄ y con 1 a q₅; q₄ tiene un bucle con 0 y va con 1 a q₁; q₅ y q₆ son de aceptación, q₅ con un bucle con 1 y con 0 a q₆, q₆ con un bucle con 0 y con 1 a q₅; q₇, de aceptación, va con 0 a q₃ y tiene un bucle con 1. Los estados de un mismo bloque tienen el mismo color, y debajo del diagrama se lee la partición. Paso 1: el autómata completo. Paso 2: q₇ se apaga, porque es inalcanzable y se quita. Paso 3: P₀, con A = {q₀, q₁, q₂, q₃, q₄} y B = {q₅, q₆}. Paso 4, ronda 1: se resalta la flecha de q₃ a q₅ con 1 y q₃ cambia de color; P₁ tiene A = {q₀, q₁, q₂, q₄}, B = {q₃} y C = {q₅, q₆}. Paso 5, ronda 2: se resalta la flecha de q₂ a q₃ con 0 y se separa q₂; P₂ tiene 4 bloques. Paso 6, ronda 3: se resalta la flecha de q₁ a q₂ con 0 y se separa q₁; P₃ tiene A = {q₀, q₄}, B = {q₁}, C = {q₂}, D = {q₃} y E = {q₅, q₆}. Paso 7, ronda 4: no se separa nada, P₄ = P₃, y una franja rodea a q₀ con q₄ y otra a q₅ con q₆, las parejas que se fundenAnimación de la minimización del autómata de 8 estados que reconoce las cadenas que contienen 1001. El diagrama: q₀ es inicial; q₀ va con 0 a q₄ y con 1 a q₁; q₁ tiene un bucle con 1 y va con 0 a q₂; q₂ va con 0 a q₃ y con 1 a q₁; q₃ va con 0 a q₄ y con 1 a q₅; q₄ tiene un bucle con 0 y va con 1 a q₁; q₅ y q₆ son de aceptación, q₅ con un bucle con 1 y con 0 a q₆, q₆ con un bucle con 0 y con 1 a q₅; q₇, de aceptación, va con 0 a q₃ y tiene un bucle con 1. Los estados de un mismo bloque tienen el mismo color, y debajo del diagrama se lee la partición. Paso 1: el autómata completo. Paso 2: q₇ se apaga, porque es inalcanzable y se quita. Paso 3: P₀, con A = {q₀, q₁, q₂, q₃, q₄} y B = {q₅, q₆}. Paso 4, ronda 1: se resalta la flecha de q₃ a q₅ con 1 y q₃ cambia de color; P₁ tiene A = {q₀, q₁, q₂, q₄}, B = {q₃} y C = {q₅, q₆}. Paso 5, ronda 2: se resalta la flecha de q₂ a q₃ con 0 y se separa q₂; P₂ tiene 4 bloques. Paso 6, ronda 3: se resalta la flecha de q₁ a q₂ con 0 y se separa q₁; P₃ tiene A = {q₀, q₄}, B = {q₁}, C = {q₂}, D = {q₃} y E = {q₅, q₆}. Paso 7, ronda 4: no se separa nada, P₄ = P₃, y una franja rodea a q₀ con q₄ y otra a q₅ con q₆, las parejas que se funden
En cada ronda se separa un estado, delatado por una flecha que lo lleva a un bloque distinto del que alcanzan sus compañeros. La separación avanza hacia atrás desde los estados de aceptación: primero q₃, después q₂, después q₁.

Sigámoslo a mano.

Antes de empezar. q7q_7 es inalcanzable y se quita. Quedan 7 estados.

P0P_0. Los estados de aceptación que quedan son q5q_5 y q6q_6:

P0={ {q0,q1,q2,q3,q4},  {q5,q6} }P_0 = \{\, \{q_0, q_1, q_2, q_3, q_4\},\; \{q_5, q_6\} \,\}

Ronda 1. En el bloque AA, todos van a AA con 0\mathtt{0}. Con 1\mathtt{1}, todos van a AA salvo q3q_3, que va a q5q_5, del bloque BB. Entonces q3q_3 se separa: con el sufijo 1\mathtt{1} llega a aceptación y los otros no. En el bloque BB, q5q_5 y q6q_6 van a BB con los dos símbolos, y siguen juntos.

P1={ {q0,q1,q2,q4},  {q3},  {q5,q6} }P_1 = \{\, \{q_0, q_1, q_2, q_4\},\; \{q_3\},\; \{q_5, q_6\} \,\}

Ronda 2. Ahora q3q_3 tiene bloque propio, y eso delata a quien llega a él: q2q_2 va a q3q_3 con 0\mathtt{0}, y los demás de su bloque no. Se separa q2q_2. El sufijo que lo distingue es 01\mathtt{01}.

P2={ {q0,q1,q4},  {q2},  {q3},  {q5,q6} }P_2 = \{\, \{q_0, q_1, q_4\},\; \{q_2\},\; \{q_3\},\; \{q_5, q_6\} \,\}

Ronda 3. Lo mismo un paso más atrás: q1q_1 va a q2q_2 con 0\mathtt{0}, y q0q_0 y q4q_4 no. Se separa q1q_1, con el sufijo 001\mathtt{001}: el que encontró distinguish.

P3={ {q0,q4},  {q1},  {q2},  {q3},  {q5,q6} }P_3 = \{\, \{q_0, q_4\},\; \{q_1\},\; \{q_2\},\; \{q_3\},\; \{q_5, q_6\} \,\}

Ronda 4. q0q_0 y q4q_4 van los dos a AA con 0\mathtt{0} y a BB con 1\mathtt{1}. q5q_5 y q6q_6 van los dos a EE con cualquier símbolo. No se separa nada: P4=P3P_4 = P_3, y el algoritmo termina.

El resultado. Cinco bloques, cinco estados. En la salida, un bloque de varios estados se llama con sus nombres entre llaves:

δ\delta 0\mathtt{0} 1\mathtt{1}
→{q0,q4}\to \{q_0, q_4\} {q0,q4}\{q_0, q_4\} q1q_1
q1q_1 q2q_2 q1q_1
q2q_2 q3q_3 q1q_1
q3q_3 {q0,q4}\{q_0, q_4\} {q5,q6}\{q_5, q_6\}
∗  {q5,q6}* \; \{q_5, q_6\} {q5,q6}\{q_5, q_6\} {q5,q6}\{q_5, q_6\}
Diagrama de estados del DFA mínimo, con cinco estados en fila: el bloque {q₀, q₄}, que es el inicial, q₁, q₂, q₃ y el bloque {q₅, q₆}, con doble círculo. El bloque {q₀, q₄} tiene un bucle con 0 y va con 1 a q₁. q₁ tiene un bucle con 1 y va con 0 a q₂. q₂ va con 0 a q₃ y vuelve con 1 a q₁. q₃ va con 1 al bloque {q₅, q₆} y vuelve con 0, por una flecha larga, al bloque {q₀, q₄}. El bloque {q₅, q₆} tiene un bucle con 0 y con 1. Debajo de cada estado, cuántas letras de 1001 lleva armadas y lo que recuerda: ningún avance; lo leído termina en 1; termina en 10; termina en 100; ya apareció 1001Diagrama de estados del DFA mínimo, con cinco estados en fila: el bloque {q₀, q₄}, que es el inicial, q₁, q₂, q₃ y el bloque {q₅, q₆}, con doble círculo. El bloque {q₀, q₄} tiene un bucle con 0 y va con 1 a q₁. q₁ tiene un bucle con 1 y va con 0 a q₂. q₂ va con 0 a q₃ y vuelve con 1 a q₁. q₃ va con 1 al bloque {q₅, q₆} y vuelve con 0, por una flecha larga, al bloque {q₀, q₄}. El bloque {q₅, q₆} tiene un bucle con 0 y con 1. Debajo de cada estado, cuántas letras de 1001 lleva armadas y lo que recuerda: ningún avance; lo leído termina en 1; termina en 10; termina en 100; ya apareció 1001
El DFA mínimo, con un estado por bloque. Cada estado dice cuánto de 1001 está armado al final de lo leído, y eso es todo lo que hace falta recordar.

Es el autómata que habríamos diseñado con el método de la semana 1: un estado por cada avance hacia 1001\mathtt{1001} y un estado final del que no se sale. Las pruebas comprueban que acepta lo mismo que el original con todas las cadenas de longitud a lo sumo 12, y que es exactamente el lenguaje de las cadenas que contienen 1001\mathtt{1001}.

Dos cosas que el ejemplo enseña.

La información viaja hacia atrás, un paso por ronda. En P0P_0 solo se sabe quién acepta. En la ronda 1 se separa el que llega a aceptación en un paso, en la ronda 2 el que llega en dos, y así. Después de la ronda kk, dos estados están en bloques distintos exactamente si los distingue algún sufijo de longitud a lo sumo kk.

Hay que quitar primero los inalcanzables. Si se refina sin quitar q7q_7, el algoritmo funciona igual, pero q7q_7 no es equivalente a ningún otro estado y se queda con un bloque propio:

$ build/minimize machines/contains_1001.dfa --todos | grep -E '^(estados|P[0-9]|DFA)'
estados: 8, alcanzables: 7. No se quita ninguno (--todos)
P0: 2 bloques
P1: 4 bloques
P2: 5 bloques
P3: 6 bloques
P4 = P3: la partición ya no cambia
DFA mínimo: 6 estados

Salen 6 estados en vez de 5. El autómata es correcto, pero no es el mínimo.

El autómata de 7 estados de Termina en 01 necesita una sola ronda:

$ build/minimize machines/ends_01_seven.dfa | grep -E '^(P[0-9]|  [A-Z] =)'
P0: 2 bloques
  A = {e, 0, 1, 00, 10, 11}
  B = {01}
P1: 3 bloques
  A = {e, 1, 11}
  B = {0, 00, 10}
  C = {01}
P2 = P1: la partición ya no cambia

Los tres bloques son las tres clases que mostró classes.

Por qué funciona

Hay que demostrar tres cosas: que el algoritmo termina, que el autómata que devuelve reconoce el mismo lenguaje, y que no hay ninguno más pequeño. Todo sale de entender qué partición hay después de cada ronda.

Sea MM el DFA después de quitar los inalcanzables. Para cada k≥0k \geq 0, digamos que p∼kqp \sim_k q si ningún sufijo de longitud a lo sumo kk distingue a pp de qq. Cuanto mayor es kk, más sufijos se prueban y más difícil es ser equivalentes: p∼k+1qp \sim_{k+1} q implica p∼kqp \sim_k q. Y p∼qp \sim q quiere decir p∼kqp \sim_k q para todo kk.

Lema (de la ronda). Para todo k≥0k \geq 0 y todos los estados pp, qq:

p∼k+1qsi y solo sip∼kq   y   δ(p,a)∼kδ(q,a) para todo a∈Σ.p \sim_{k+1} q \quad\text{si y solo si}\quad p \sim_k q \;\text{ y }\; \delta(p, a) \sim_k \delta(q, a) \text{ para todo } a \in \Sigma.

Demostración. Las dos direcciones, por la definición.

(⇒\Rightarrow) Supongamos p∼k+1qp \sim_{k+1} q. Entonces p∼kqp \sim_k q, porque los sufijos de longitud a lo sumo kk están entre los de longitud a lo sumo k+1k + 1. Sea aa un símbolo y zz un sufijo con ∣z∣≤k|z| \leq k. La cadena azaz mide a lo sumo k+1k + 1, así que no distingue a pp de qq: δ∗(p,az)∈F  ⟺  δ∗(q,az)∈F\delta^*(p, az) \in F \iff \delta^*(q, az) \in F. Como δ∗(p,az)=δ∗(δ(p,a),z)\delta^*(p, az) = \delta^*(\delta(p, a), z), y lo mismo con qq, eso dice que zz no distingue a δ(p,a)\delta(p, a) de δ(q,a)\delta(q, a). Vale para toda zz con ∣z∣≤k|z| \leq k: δ(p,a)∼kδ(q,a)\delta(p, a) \sim_k \delta(q, a).

(⇐\Leftarrow) Supongamos el lado derecho, y sea ww un sufijo con ∣w∣≤k+1|w| \leq k + 1. Si w=εw = \varepsilon, no distingue a pp de qq porque p∼kqp \sim_k q. Si no, w=azw = az con ∣z∣≤k|z| \leq k, y δ∗(p,az)=δ∗(δ(p,a),z)\delta^*(p, az) = \delta^*(\delta(p, a), z), y lo mismo con qq. Como δ(p,a)∼kδ(q,a)\delta(p, a) \sim_k \delta(q, a), la cadena zz no los distingue, así que ww no distingue a pp de qq. ∎

Teorema (la minimización es correcta). Sea PkP_k la partición después de kk rondas. Entonces:

  1. Dos estados están en el mismo bloque de PkP_k si y solo si p∼kqp \sim_k q.
  2. El algoritmo termina después de a lo sumo ∣Q∣|Q| rondas, y la partición final es la de ∼\sim.
  3. El autómata cociente reconoce L(M)L(M).
  4. Ningún DFA que reconozca L(M)L(M) tiene menos estados.

Demostración de 1. Por inducción sobre kk. Caso base: el único sufijo de longitud 0 es ε\varepsilon, y δ∗(p,ε)=p\delta^*(p, \varepsilon) = p. Entonces p∼0qp \sim_0 q dice que pp y qq están los dos en FF o los dos fuera, y eso es estar en el mismo bloque de P0={F,Q−F}P_0 = \{F, Q - F\}. Paso inductivo: la ronda k+1k + 1 deja juntos a pp y qq si tienen la misma firma, es decir, si están en el mismo bloque de PkP_k y, para cada símbolo aa, δ(p,a)\delta(p, a) y δ(q,a)\delta(q, a) están en el mismo bloque de PkP_k. Por la hipótesis de inducción, eso es p∼kqp \sim_k q y δ(p,a)∼kδ(q,a)\delta(p, a) \sim_k \delta(q, a) para todo aa. Por el lema de la ronda, eso es p∼k+1qp \sim_{k+1} q.

Demostración de 2. Cada ronda que cambia la partición aumenta el número de bloques al menos en uno. Hay al menos un bloque al empezar y nunca más de ∣Q∣|Q|, así que a lo sumo ∣Q∣−1|Q| - 1 rondas cambian algo, y la siguiente es la que no cambia nada.

Falta ver que, cuando una ronda no cambia nada, la partición ya es la de ∼\sim. Si Pk+1=PkP_{k+1} = P_k, las relaciones ∼k+1\sim_{k+1} y ∼k\sim_k son la misma. El lema de la ronda calcula ∼k+2\sim_{k+2} a partir de ∼k+1\sim_{k+1} con la misma regla con la que calcula ∼k+1\sim_{k+1} a partir de ∼k\sim_k: con el mismo dato, da el mismo resultado, y ∼k+2\sim_{k+2} es otra vez la misma relación. Repitiendo el argumento, ∼m\sim_m es igual a ∼k\sim_k para todo m≥km \geq k. Como p∼qp \sim q quiere decir p∼mqp \sim_m q para todo mm, la partición final es la de ∼\sim.

Demostración de 3. Escribimos [p][p] para el bloque de pp en la partición final. Por la parte 2, [p]=[q][p] = [q] si y solo si p∼qp \sim q. El autómata cociente es

M′=(Q′,Σ,δ′,[q0],F′),Q′={ [p]:p∈Q },δ′([p],a)=[δ(p,a)],F′={ [p]:p∈F }.M' = (Q', \Sigma, \delta', [q_0], F'), \qquad Q' = \{\, [p] : p \in Q \,\}, \quad \delta'([p], a) = [\delta(p, a)], \quad F' = \{\, [p] : p \in F \,\}.

Está bien definido. Hay que ver que δ′\delta' y F′F' no dependen del representante. Sea [p]=[q][p] = [q], es decir, p∼qp \sim q, y sea aa un símbolo. Si algún sufijo zz distinguiera a δ(p,a)\delta(p, a) de δ(q,a)\delta(q, a), entonces azaz distinguiría a pp de qq, porque δ∗(p,az)=δ∗(δ(p,a),z)\delta^*(p, az) = \delta^*(\delta(p, a), z) y lo mismo con qq. No puede ser. Luego δ(p,a)∼δ(q,a)\delta(p, a) \sim \delta(q, a), es decir, [δ(p,a)]=[δ(q,a)][\delta(p, a)] = [\delta(q, a)]. Y como el sufijo ε\varepsilon no distingue a pp de qq, los dos están en FF o ninguno.

Reconoce el mismo lenguaje. Para todo estado pp y toda cadena ww, δ′∗([p],w)=[δ∗(p,w)]\delta'^*([p], w) = [\delta^*(p, w)]. Por inducción sobre ∣w∣|w|: para w=εw = \varepsilon los dos lados son [p][p]; y si w=uaw = ua,

δ′∗([p],ua)=δ′(δ′∗([p],u),a)=δ′([δ∗(p,u)],a)=[δ(δ∗(p,u),a)]=[δ∗(p,ua)].\delta'^*([p], ua) = \delta'(\delta'^*([p], u), a) = \delta'([\delta^*(p, u)], a) = [\delta(\delta^*(p, u), a)] = [\delta^*(p, ua)].

Entonces M′M' acepta ww si y solo si [δ∗(q0,w)]∈F′[\delta^*(q_0, w)] \in F', si y solo si δ∗(q0,w)∈F\delta^*(q_0, w) \in F, si y solo si MM acepta ww. El paso del medio usa que F′F' está bien definido: un bloque está en F′F' exactamente cuando sus estados están en FF.

Demostración de 4. Con cadenas distinguibles. Como en MM todos los estados son alcanzables, para cada bloque [p][p] podemos elegir una cadena xpx_p con δ∗(q0,xp)=p\delta^*(q_0, x_p) = p. Sean [p]≠[q][p] \neq [q] dos bloques distintos. Entonces p≁qp \not\sim q: algún sufijo zz distingue a pp de qq, es decir, exactamente uno de δ∗(p,z)\delta^*(p, z) y δ∗(q,z)\delta^*(q, z) está en FF. Pero δ∗(p,z)=δ∗(q0,xpz)\delta^*(p, z) = \delta^*(q_0, x_pz), y lo mismo con qq: exactamente una de xpzx_pz y xqzx_qz está en L(M)L(M). Luego xpx_p y xqx_q son distinguibles respecto de L(M)L(M).

Tenemos una cadena por bloque, y son distinguibles dos a dos. Por el teorema de la cota inferior, todo DFA que reconoce L(M)L(M) tiene al menos tantos estados como bloques hay, que son los estados de M′M'. ∎

De la parte 2 sale también la cota que usa distinguish. A lo sumo ∣Q∣−1|Q| - 1 rondas cambian algo, así que P∣Q∣−1P_{|Q|-1} ya es la partición final: si dos estados se pueden distinguir, los distingue algún sufijo de longitud a lo sumo ∣Q∣−1|Q| - 1. Las partes 1 y 2 no usan que los estados sean alcanzables, y la cota vale para cualquier DFA.

La parte 4 es el único lugar donde se usa el paso 1 del algoritmo. Para un estado inalcanzable no existe la cadena xpx_p, y por eso con q7q_7 salía un estado de más.

Juntando la parte 4 con Myhill-Nerode: los bloques finales corresponden a las clases de ≡L(M)\equiv_{L(M)}, una por bloque, y el autómata cociente es el autómata de las clases MLM_L con otros nombres. Las pruebas de la semana comparan los dos, para todos los autómatas de machines/.

Cuánto cuesta

Sea n=∣Q∣n = |Q|. Una ronda calcula nn firmas de ∣Σ∣+1|\Sigma| + 1 números y agrupa los estados que tienen la misma: con una tabla hash, O(n⋅∣Σ∣)O(n \cdot |\Sigma|) operaciones. Hay a lo sumo nn rondas. En total, el algoritmo de Moore cuesta O(n2⋅∣Σ∣)O(n^2 \cdot |\Sigma|) en el peor caso.

El peor caso existe: un ciclo de nn estados con uno solo de aceptación necesita del orden de nn rondas, porque en cada una se separa un estado más. Pero en muchos autómatas las rondas son pocas. El de LkL_k, con 2k2^k estados, necesita k−1k - 1 rondas que cambien algo:

$ build/kth_from_end --tabla 10
 k  estados del NFA  estados del DFA  después de minimizar  rondas con cambios
 1                2                2                     2                   0
 2                3                4                     4                   1
 3                4                8                     8                   2
 4                5               16                    16                   3
 5                6               32                    32                   4
 6                7               64                    64                   5
 7                8              128                   128                   6
 8                9              256                   256                   7
 9               10              512                   512                   8
10               11             1024                  1024                   9

La tabla dice además lo que ya demostramos: al minimizar el autómata de 2k2^k estados no se fusiona ninguno.

Existe un algoritmo más rápido, el de Hopcroft, que cuesta O(nlog⁡n⋅∣Σ∣)O(n \log n \cdot |\Sigma|). En vez de revisar todos los estados en cada ronda, lleva una lista de bloques pendientes y solo revisa los estados que tienen una transición hacia el bloque que está procesando. Es el que usan las bibliotecas de autómatas. No lo vamos a estudiar: calcula la misma partición, y el de Moore alcanza para todo lo que hace el curso.

En C++. En minimize.h, una partición es un std::map que le da a cada estado el número de su bloque. La firma de un estado es un std::vector<int>, y los estados se agrupan con un std::map<std::vector<int>, int>, que le asigna un número nuevo a cada firma distinta la primera vez que aparece:

inline Partition refine(const Dfa& m, const Partition& p) {
    std::map<std::string, std::vector<int>> signature;
    for (const std::string& state : m.states) {
        std::vector<int> key = {p.block.at(state)};
        for (char a : m.alphabet) {
            key.push_back(p.block.at(step(m, state, a)));
        }
        signature[state] = key;
    }
    return group_by(m, signature);
}

Un std::vector se puede usar como clave de un std::map porque los vectores se comparan en orden lexicográfico. Con el std::map cada búsqueda cuesta un factor log⁡n\log n más que con una tabla hash; para el laboratorio alcanza.

El DFA mínimo es único

Dos personas que minimizan el mismo autómata, o dos autómatas distintos del mismo lenguaje, ¿obtienen lo mismo? Los nombres de los estados pueden cambiar, pero nada más.

Dos DFA son iguales salvo los nombres de los estados si hay una biyección hh entre sus conjuntos de estados que respeta todo: lleva el estado inicial al inicial, los de aceptación a los de aceptación y los demás a los demás, y cumple h(δ1(q,a))=δ2(h(q),a)h(\delta_1(q, a)) = \delta_2(h(q), a) para todo estado y todo símbolo. Dibujados, son el mismo diagrama con otras etiquetas en los círculos.

Teorema (unicidad). Sea LL un lenguaje regular cuya relación ≡L\equiv_L tiene kk clases. Todo DFA con kk estados que reconoce LL es igual, salvo los nombres de los estados, al autómata de las clases MLM_L. En particular, dos DFA mínimos de LL son iguales salvo los nombres.

Demostración. Por construcción de la biyección. Sea M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) un DFA con kk estados y L(M)=LL(M) = L.

Todos los estados de MM son alcanzables. Si alguno no lo fuera, al quitarlo quedaría un DFA de LL con menos de kk estados, y por Myhill-Nerode no existe.

La función. Para cada estado qq elegimos una cadena xx que llegue a él, δ∗(q0,x)=q\delta^*(q_0, x) = q, y definimos h(q)=[x]h(q) = [x], la clase de xx. No depende de la cadena elegida: si xx e yy llegan las dos a qq, por el lema de los estados distintos son indistinguibles, y [x]=[y][x] = [y].

Es una biyección. Toda clase [x][x] es la imagen de algún estado, el estado δ∗(q0,x)\delta^*(q_0, x): hh es sobreyectiva. Y va de un conjunto de kk elementos a otro de kk elementos, así que una función sobreyectiva entre ellos es también inyectiva.

Respeta el autómata. El estado inicial: ε\varepsilon llega a q0q_0, así que h(q0)=[ε]h(q_0) = [\varepsilon], el inicial de MLM_L. Las transiciones: si xx llega a qq, entonces xaxa llega a δ(q,a)\delta(q, a), así que h(δ(q,a))=[xa]h(\delta(q, a)) = [xa], que es δL([x],a)=δL(h(q),a)\delta_L([x], a) = \delta_L(h(q), a). La aceptación: q∈Fq \in F si y solo si MM acepta xx, si y solo si x∈Lx \in L, si y solo si [x][x] es de aceptación en MLM_L.

Dos DFA mínimos de LL tienen kk estados cada uno. Los dos son iguales a MLM_L salvo los nombres, y entonces lo son entre sí. ∎

El ejemplo está a la mano. La semana 1 diseñó el autómata de 3 estados de Termina en 01 pensando qué recordar. Esta semana minimizamos el de 7 estados con un algoritmo que no piensa nada. Tienen que haber llegado a lo mismo:

$ build/equivalent machines/ends_01_seven.dfa machines/ends_01.dfa
machines/ends_01_seven.dfa: 7 estados, mínimo de 3
machines/ends_01.dfa: 3 estados, mínimo de 3
los dos mínimos son el mismo autómata salvo los nombres: reconocen el mismo lenguaje

La correspondencia es {e,1,11}↦q0\{e, 1, 11\} \mapsto q_0, {0,00,10}↦q1\{0, 00, 10\} \mapsto q_1 y 01↦q201 \mapsto q_2.

La unicidad vale para los DFA. Un lenguaje puede tener varios NFA mínimos que no se parecen entre sí, y minimizar un NFA es un problema mucho más difícil, que no veremos.

Decidir si dos DFA son equivalentes

La unicidad da un algoritmo para una pregunta que hasta ahora respondíamos probando cadenas: ¿dos DFA sobre el mismo alfabeto reconocen el mismo lenguaje?

  1. Minimizar los dos.
  2. Comprobar si los mínimos son iguales salvo los nombres.

Si L(M1)=L(M2)L(M_1) = L(M_2), los dos mínimos son DFA mínimos del mismo lenguaje, y por el teorema son iguales salvo los nombres. Si los lenguajes son distintos, los mínimos reconocen lenguajes distintos y no pueden ser iguales.

El paso 2 no exige probar todas las biyecciones. Si hay una, está forzada: el inicial va al inicial y, si pp va a qq, entonces δ1(p,a)\delta_1(p, a) va a δ2(q,a)\delta_2(q, a). Basta recorrer los dos autómatas a la vez desde los iniciales, anotando la correspondencia, y parar si aparece una contradicción: un estado al que le tocarían dos compañeros, o un par en el que uno acepta y el otro no. Es la función isomorphic de minimize.h. Cuando los lenguajes son distintos, el programa muestra además la cadena más corta que los separa:

$ build/equivalent machines/contains_101.dfa machines/contains_1001.dfa
machines/contains_101.dfa: 4 estados, mínimo de 4
machines/contains_1001.dfa: 8 estados, mínimo de 5
los mínimos son distintos: no reconocen el mismo lenguaje
la cadena más corta que los separa: 101 (la acepta el primero)

Hay otro algoritmo, que salía del ejercicio 13 de la semana 1: construir el producto de los dos autómatas y buscar un par alcanzable (p,q)(p, q) en el que exactamente uno acepte. Los dos son correctos. Lo importante es que la pregunta tiene un algoritmo que siempre termina y siempre responde bien. En la semana 9 ese hecho tendrá nombre, ”EQDFA\mathrm{EQ}_{\mathrm{DFA}} es decidible”, y lo compararemos con la misma pregunta para modelos más potentes, donde la respuesta es otra.

En la práctica. Minimizar es el último paso del camino clásico para generar un analizador léxico, el que describen los textos de compiladores: de las expresiones regulares de los tokens a un NFA, del NFA a un DFA con la construcción de subconjuntos, y de ese DFA a su mínimo, para que la tabla de transiciones que se escribe en el programa ocupe lo menos posible. Y como el mínimo es único, sirve de forma canónica: para saber si dos expresiones regulares describen el mismo lenguaje, se llevan las dos hasta su DFA mínimo y se comparan.

Streaming: una cota inferior de memoria

Esta sección es opcional.

Un algoritmo de streaming procesa datos que llegan uno tras otro y que son demasiados para guardarlos: los paquetes que pasan por un router, las líneas de un registro de eventos, las lecturas de un sensor. Lee cada dato una sola vez, en orden, y mantiene una memoria pequeña que actualiza con cada uno. Al final, o en cualquier momento, responde una pregunta sobre todo lo que vio.

Dicho así, es un autómata. Supongamos que los datos son símbolos de un alfabeto Σ\Sigma, que la pregunta es de sí o no, y que el algoritmo es determinista y usa ss bits de memoria, sea cual sea la longitud de la entrada. El contenido de la memoria es una de 2s2^s combinaciones posibles. Cada símbolo que llega cambia ese contenido de una manera que depende solo del contenido anterior y del símbolo. Y la respuesta final depende solo del contenido final. Aquí “memoria” es todo lo que cambia mientras el algoritmo lee: sus variables y también, si las tiene, el punto del programa en el que va. Eso es un DFA:

El algoritmo El DFA
Un contenido posible de la memoria Un estado: hay a lo sumo 2s2^s
El contenido al empezar q0q_0
Cómo se actualiza con cada dato δ\delta
Los contenidos con los que responde sí FF
Las entradas con las que responde sí L(M)L(M)

Entonces todo lo que sabemos sobre el número de estados dice algo sobre la memoria.

Teorema. Si un algoritmo de streaming determinista con ss bits de memoria decide un lenguaje LL, y hay kk cadenas distinguibles dos a dos respecto de LL, entonces s≥log⁡2ks \geq \log_2 k.

Demostración. El algoritmo es un DFA que reconoce LL con a lo sumo 2s2^s estados. Por el teorema de la cota inferior tiene al menos kk. Luego 2s≥k2^s \geq k. ∎

Es una cota inferior: no habla de un algoritmo concreto, sino de todos. Ningún programador, por ingenioso que sea, puede resolver el problema con menos memoria.

Un ejemplo completo. Un servicio emite una señal por segundo: 1\mathtt{1} si hubo un error y 0\mathtt{0} si no. En cualquier momento se nos puede preguntar: ¿hubo un error hace exactamente kk segundos? Es decir, ¿el kk-ésimo símbolo desde el final es 1\mathtt{1}? Es el lenguaje LkL_k.

  • Cota inferior. Las 2k2^k cadenas de longitud kk son distinguibles dos a dos respecto de LkL_k, como demostramos arriba. Por el teorema, cualquier algoritmo necesita s≥log⁡22k=ks \geq \log_2 2^k = k bits.
  • Cota superior. Guardar los últimos kk símbolos en un registro de kk bits, que se desplaza con cada dato, resuelve el problema. Es el struct Window de streaming.h: al leer un símbolo hace bits = ((bits << 1) | nuevo) & mask, y para responder mira el bit más antiguo.

Las dos cotas coinciden: hacen falta exactamente kk bits. Para preguntar por lo que pasó hace una hora, son 3600 bits, y no existe ninguna manera de resumirlos. Las pruebas comprueban que el registro responde igual que el DFA de 2k2^k estados, y que sus 2k2^k contenidos posibles son, uno por uno, los estados.

Para un lenguaje que no es regular, ninguna cantidad fija de memoria alcanza. Pero el mismo argumento todavía mide cómo crece la memoria con la longitud de la entrada. Tomemos EE, tantos ceros como unos, y un algoritmo que solo tiene que acertar con las entradas de longitud a lo sumo nn. Las cadenas 00,01,…,0⌊n/2⌋\mathtt{0}^0, \mathtt{0}^1, \ldots, \mathtt{0}^{\lfloor n/2 \rfloor} se distinguen dos a dos con sufijos que no pasan de esa longitud: para i<ji < j, el sufijo 1i\mathtt{1}^i da 0i1i∈E\mathtt{0}^i\mathtt{1}^i \in E y 0j1i∉E\mathtt{0}^j\mathtt{1}^i \notin E, y las dos miden a lo sumo nn. El lema de los estados distintos sigue valiendo, porque solo usa esas cadenas: después de leer 0i\mathtt{0}^i y 0j\mathtt{0}^j la memoria tiene que ser distinta. Son ⌊n/2⌋+1\lfloor n/2 \rfloor + 1 contenidos distintos, y hacen falta al menos log⁡2(⌊n/2⌋+1)\log_2(\lfloor n/2 \rfloor + 1) bits. Un contador de la diferencia entre ceros y unos lo resuelve con unos log⁡2(2n+1)\log_2(2n + 1) bits, así que la respuesta correcta es “del orden de log⁡n\log n”, y ya no se puede mejorar más que en una constante.

En la práctica. Con el mismo argumento se demuestra que contar exactamente cuántos elementos distintos tiene un flujo, por ejemplo cuántos usuarios distintos visitaron un sitio, necesita una memoria proporcional al número de elementos posibles. Por eso los sistemas reales no lo calculan exactamente: estiman, con estructuras probabilísticas como HyperLogLog, que usan unos pocos kilobytes y aceptan un error pequeño. Una cota inferior no es una mala noticia: dice cuándo dejar de buscar el algoritmo exacto y cambiar la pregunta.

El código de la semana

code/week-04/
├── dfa.h                 el struct Dfa de la semana 1, sin cambios
├── pumping.h             la división del lema sacada de un DFA; las partidas del juego
├── distinguish.h         sufijos que distinguen; conjuntos distinguibles; el autómata de las clases
├── minimize.h            particiones, rondas de Moore, autómata cociente, igualdad salvo nombres
├── streaming.h           el registro de k bits y el contador
├── show_dfa.cpp          muestra un .dfa como quíntupla y como tabla (semana 1)
├── run_dfa.cpp           la ejecución de un DFA con una o más cadenas (semana 1)
├── pump.cpp              la división x, y, z de una cadena, y las cadenas bombeadas
├── pumping_game.cpp      una partida completa del juego para un p concreto
├── distinguish.cpp       ¿dos cadenas son distinguibles? por fuerza bruta
├── fooling_set.cpp       comprueba un conjunto de cadenas distinguibles dos a dos
├── classes.cpp           las clases de equivalencia del lenguaje de un DFA
├── kth_from_end.cpp      escribe el DFA de 2^k estados de L_k
├── minimize.cpp          minimiza un DFA y muestra cada ronda
├── equivalent.cpp        decide si dos DFA reconocen el mismo lenguaje
├── machines/             los autómatas del capítulo, en formato .dfa
├── test_pumping.cpp      el lema en autómatas reales; las cinco demostraciones, división por división
├── test_distinguish.cpp  cadenas distinguibles, la cota 2^k, Myhill-Nerode, streaming
├── test_minimize.cpp     las particiones del ejemplo; el mínimo es equivalente y no se reduce más
└── lab/minimize_dfa/     el ejercicio opcional de laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan.

$ make test
test_pumping: ok
test_distinguish: ok
test_minimize: ok
Todas las pruebas pasaron.

Las pruebas comprueban con assert lo que este capítulo afirma sobre máquinas y cadenas concretas.

  • test_pumping revisa que la división de pump cumple las tres condiciones del lema en siete autómatas. Para las cinco demostraciones de la sesión A, juega la partida con pp de 1 a 12 y comprueba que en todas las divisiones permitidas yy es solo ceros y que el exponente elegido saca la cadena del lenguaje. Comprueba también que las cadenas mal elegidas dejan una división que resiste, y que el lenguaje TT se deja bombear con p=2p = 2 en todas sus cadenas de longitud entre 2 y 8.
  • test_distinguish revisa los sufijos de las demostraciones de la sesión B. Para kk de 1 a 6, comprueba que las 2k2^k cadenas de longitud kk son distinguibles dos a dos con el sufijo 0i−1\mathtt{0}^{i-1}, que la fuerza bruta y el recorrido de pares de estados dan sufijos igual de cortos, y que el autómata de las clases es igual, salvo nombres, al que devuelve la minimización.
  • test_minimize comprueba las cuatro particiones del ejemplo, una por una, y que PkP_k separa exactamente a los estados que se distinguen con sufijos de longitud a lo sumo kk. Para cada autómata, el mínimo acepta lo mismo que el original con todas las cadenas de longitud a lo sumo 12, tiene el número de estados de la tabla siguiente, y sus estados son alcanzables y distinguibles dos a dos. También minimiza 120 autómatas al azar y compara el número de estados con un conteo por fuerza bruta.

Los archivos de machines/ son:

Archivo Lenguaje Estados Estados del mínimo
count_attempt.dfa El intento fallido para 0n1n\mathtt{0}^n\mathtt{1}^n 8 8
multiple_of_3.dfa Múltiplos de 3 en binario (semana 1) 3 3
multiple_of_3_mod6.dfa Múltiplos de 3, llevando el resto entre 6 6 3
ends_01.dfa Termina en 01\mathtt{01} (semana 1) 3 3
ends_01_seven.dfa Termina en 01\mathtt{01}, recordando dos símbolos 7 3
contains_101.dfa Contiene 101\mathtt{101} (semana 1) 4 4
contains_1001.dfa Contiene 1001\mathtt{1001}, con estados de más 8 5
last_3.dfa El tercer símbolo desde el final es 1\mathtt{1} 8 8

Como en la semana 1, δ\delta es un std::map con los nombres de los estados como cadenas. Se eligió para que el código se lea como las definiciones. En el laboratorio conviene numerar los estados y trabajar con enteros.

El laboratorio

La sesión de laboratorio de esta semana es para la Práctica 1. El problema de lab/minimize_dfa queda como ejercicio opcional: leer un DFA en formato .dfa y escribir, en el mismo formato, el DFA mínimo equivalente.

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

Hay muchas respuestas correctas, porque los estados del resultado pueden llamarse de cualquier manera y escribirse en cualquier orden. Por eso el juez usa un verificador: comprueba que la salida sea un DFA bien formado, que reconozca el mismo lenguaje que la entrada y que tenga el número mínimo de estados. Por el teorema de unicidad, con eso basta para saber que es el mínimo. Los casos incluyen estados inalcanzables, un autómata sin estados de aceptación, uno con todos de aceptación, uno que ya es mínimo, y cuatro entradas grandes en las que decidir cada par de estados por separado da TLE. El enunciado está en el README.md de esa carpeta.

Resumen

  • En un DFA con pp estados, toda ejecución de pp pasos o más repite un estado, y el tramo leído entre las dos visitas se puede quitar o repetir sin cambiar el estado final.
  • Lema de bombeo: si AA es regular, hay un pp tal que toda s∈As \in A con ∣s∣≥p|s| \geq p se divide en s=xyzs = xyz con xyiz∈Axy^iz \in A para todo i≥0i \geq 0, ∣y∣>0|y| > 0 y ∣xy∣≤p|xy| \leq p.
  • Para demostrar que un lenguaje no es regular se usa como un juego: el adversario elige pp, nosotros ss, el adversario la división, nosotros ii. No conocemos pp ni elegimos la división: el argumento cubre todas las que cumplen ∣y∣>0|y| > 0 y ∣xy∣≤p|xy| \leq p.
  • La cadena se elige para que ∣xy∣≤p|xy| \leq p arrincone a yy, y en el borde de la condición del lenguaje. El exponente puede ser i=0i = 0: bombear hacia abajo.
  • Con las propiedades de cierre: si LL fuera regular, L∩RL \cap R lo sería para todo RR regular. Se usa para llegar a un lenguaje que ya se sabe que no es regular.
  • El lema no demuestra que un lenguaje es regular. Hay lenguajes no regulares que lo cumplen.
  • xx e yy son distinguibles respecto de LL si algún sufijo zz deja a exactamente una de xzxz, yzyz en LL. Dos cadenas distinguibles no pueden terminar en el mismo estado de un DFA de LL.
  • kk cadenas distinguibles dos a dos obligan a tener al menos kk estados. Infinitas: el lenguaje no es regular.
  • “El kk-ésimo símbolo desde el final es 1\mathtt{1}” necesita exactamente 2k2^k estados en un DFA, y k+1k + 1 en un NFA.
  • Myhill-Nerode: LL es regular si y solo si ≡L\equiv_L tiene finitas clases de equivalencia, y ese número es el de estados del DFA mínimo. Las clases son los estados: δ([x],a)=[xa]\delta([x], a) = [xa].
  • Minimizar: quitar los estados inalcanzables, partir de {F,Q−F}\{F, Q - F\} y refinar hasta que no cambie: dos estados siguen juntos si con cada símbolo van al mismo bloque. Después de la ronda kk, están separados los estados que se distinguen con sufijos de longitud a lo sumo kk.
  • Dos estados se fusionan solo si ningún sufijo los distingue, no porque se parezcan.
  • El DFA mínimo es único salvo los nombres de los estados. Por eso se puede decidir si dos DFA son equivalentes: se minimizan y se comparan.
  • Opcional. Un algoritmo de streaming con ss bits de memoria es un DFA con a lo sumo 2s2^s estados: kk cadenas distinguibles obligan a usar al menos log⁡2k\log_2 k bits.

Ejercicios

  1. Para cada división de s=000111s = \mathtt{000111} con ∣xy∣≤3|xy| \leq 3 y ∣y∣>0|y| > 0, escriban xy0zxy^0z y xy3zxy^3z y digan si están en { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\}. ¿Cuántas divisiones hay? ¿Cuántas habría sin la condición ∣xy∣≤3|xy| \leq 3, y en cuáles de esas yy tiene ceros y unos? Comprueben la primera parte con build/pumping_game 0n1n 3.
  2. Corran build/pump machines/contains_101.dfa 0110100 y expliquen la división que sale: ¿qué estado se repite y cuál es el ciclo? Después elijan una cadena de longitud 6 que el autómata rechace y repitan. ¿Qué dice el lema, tal como está enunciado, sobre las cadenas que no están en el lenguaje? ¿Y la demostración?
  3. Demuestren con el lema de bombeo que { anbm:n≤m }\{\, \mathtt{a}^n\mathtt{b}^m : n \leq m \,\} no es regular. Escriban las cuatro jugadas. ¿Qué cadena eligen y por qué? ¿Se gana bombeando hacia arriba o hacia abajo?
  4. Demuestren lo mismo con un conjunto infinito de cadenas distinguibles. Comparen la longitud de las dos demostraciones.
  5. Alguien escribe: ”L={ 0n1n }L = \{\, \mathtt{0}^n\mathtt{1}^n \,\} no es regular. Demostración: sea s=0p1ps = \mathtt{0}^p\mathtt{1}^p, y sea x=εx = \varepsilon, y=0py = \mathtt{0}^p, z=1pz = \mathtt{1}^p. Entonces xy2z=02p1p∉Lxy^2z = \mathtt{0}^{2p}\mathtt{1}^p \notin L.” Digan qué jugada está mal y por qué eso invalida el argumento. Después expliquen por qué el lema de bombeo no demuestra que un lenguaje es regular, escribiendo su forma lógica.
  6. Demuestren que no son regulares: (a) los palíndromos sobre {0,1}\{\mathtt{0}, \mathtt{1}\}; (b) { 0n1m:n≠m }\{\, \mathtt{0}^n\mathtt{1}^m : n \neq m \,\}, usando propiedades de cierre; (c) { 1q:q es primo }\{\, \mathtt{1}^q : q \text{ es primo} \,\}, con el lema de bombeo y el exponente i=q+1i = q + 1, donde qq es la longitud de la cadena que eligieron.
  7. Para cada lenguaje, digan si es regular. Si lo es, den un DFA o una expresión regular; si no, demuéstrenlo. (a) { 0n1m:n+m es par }\{\, \mathtt{0}^n\mathtt{1}^m : n + m \text{ es par} \,\}. (b) { w:w tiene tantas apariciones de 01 como de 10 }\{\, w : w \text{ tiene tantas apariciones de } \mathtt{01} \text{ como de } \mathtt{10} \,\}. (c) { 0n1n:n≤100 }\{\, \mathtt{0}^n\mathtt{1}^n : n \leq 100 \,\}. (d) { w#w:w∈{0,1}∗ }\{\, w\mathtt{\#}w : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\}. El (b) tiene trampa: prueben con cadenas cortas antes de decidir.
  8. ¿Cuántos estados tiene el DFA mínimo de las cadenas binarias cuyo valor es múltiplo de 5? Den el autómata y justifiquen que no se puede con menos, con cinco cadenas distinguibles dos a dos y el sufijo de cada par. Comprueben su conjunto con build/fooling_set.
  9. Describan las clases de equivalencia de ≡L\equiv_L para: (a) las cadenas con una cantidad par de unos; (b) las cadenas que contienen 101\mathtt{101}; (c) { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\}. En (a) y (b), comparen con lo que imprime build/classes. En (c), ¿en qué clase están las cadenas que no son prefijo de ninguna cadena del lenguaje?
  10. Minimicen a mano el autómata de machines/multiple_of_3_mod6.dfa, de seis estados, mostrando la partición después de cada ronda. Comprueben con build/minimize. Den la correspondencia entre el resultado y el autómata de 3 estados de la semana 1, y expliquen con aritmética por qué s1s_1 y s4s_4 son equivalentes.
  11. Construyan con el programa product de la semana 1 la intersección de Termina en 01 y Contiene 101, y minimícenla. ¿Cuántos estados tenía el producto, cuántos eran alcanzables y cuántos tiene el mínimo? Den un sufijo que distinga a cada par de estados del mínimo.
  12. Den un DFA de nn estados, para n≥3n \geq 3 cualquiera, en el que el refinamiento necesite n−2n - 2 rondas que cambien algo. ¿Qué tienen que ver las rondas con la longitud de los sufijos que distinguen a los estados? Después expliquen por qué, con un alfabeto de dos símbolos, un DFA mínimo al que le basta una sola ronda que cambie algo tiene a lo sumo 8 estados.
  13. Para programar. Agreguen a minimize.h una función que reciba un DFA y diga si su lenguaje es finito, sin probar cadenas. Pista: minimicen, quiten el estado trampa si lo hay, y busquen un ciclo. ¿Qué tiene que ver con el lema de bombeo? Pruébenla con los autómatas de machines/.
  14. Para programar. Escriban un programa que reciba dos archivos .dfa y decida si reconocen el mismo lenguaje con el producto, sin minimizar. Compárenlo con build/equivalent en todos los pares de autómatas de machines/. ¿Cuál de los dos algoritmos da además un DFA que sirve para otras cosas?
  15. Opcional. Un flujo de símbolos de {0,1}\{\mathtt{0}, \mathtt{1}\}, y la pregunta: ¿hay algún 1\mathtt{1} entre los últimos kk símbolos? Den un algoritmo y cuenten sus bits de memoria. Después den una cota inferior con cadenas distinguibles. ¿Coinciden? Comparen con los kk bits de LkL_k y expliquen la diferencia.