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

Apuntes · Capítulo 6Lenguajes libres de contexto

Autómatas de pila y los límites de las gramáticas

Autómatas de pila y los límites de las gramáticas

La semana pasada apareció una clase de lenguajes más grande que la de los regulares: los que genera una gramática libre de contexto (CFG). Con reglas como S→0S1∣εS \to \mathtt{0}S\mathtt{1} \mid \varepsilon describimos { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\}, los paréntesis balanceados y las expresiones aritméticas, que ningún autómata finito reconoce. Pero una gramática es una manera de generar cadenas. Para decidir si una cadena dada está en el lenguaje tuvimos que pasar a la forma normal de Chomsky y llenar la tabla de CYK.

Con los lenguajes regulares teníamos las dos caras: la expresión regular, que describe, y el autómata, que lee la cadena y responde. Esta semana construimos la segunda cara de los lenguajes libres de contexto. La máquina es un autómata finito al que se le agrega lo único que le faltaba para contar sin tope, una pila. Se llama autómata de pila (pushdown automaton), o PDA.

La semana tiene dos mitades.

  • En la primera definimos el PDA, diseñamos varios y demostramos que es exactamente tan capaz como las gramáticas: un lenguaje tiene una gramática libre de contexto si y solo si algún PDA lo reconoce. Son dos construcciones, una en cada sentido.
  • En la segunda buscamos el límite, como hicimos en la semana 4 con los regulares. Hay un lema de bombeo para los lenguajes libres de contexto, y con él demostramos que { anbncn }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n \,\} y { ww }\{\, ww \,\} no lo son. Después vemos bajo qué operaciones se conserva la clase y bajo cuáles no, y cerramos la parte 2 del curso con el mapa de lo que llevamos.

Al final hay una sección opcional sobre cómo trabaja el parser de un compilador real, que no usa ni CYK ni una búsqueda como la de esta semana.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Un autómata finito con una pila y La definición formal de un PDA. Antes de la sesión B, Un lenguaje que pide comparar tres cantidades. Con eso llegan con la máquina ya vista y con la pregunta de la segunda sesión planteada.

En clase: Sesión A, de Un autómata finito con una pila a El PDA determinista reconoce menos. De la sección De PDA a gramática se ven en clase la idea y el ejemplo; la demostración completa queda para leer. Sesión B, de Un lenguaje que pide comparar tres cantidades a El mapa hasta ahora.

Después de clase: el Resumen y los Ejercicios, para repasar. La demostración, completa dentro de De PDA a gramática, con lápiz y papel. Antes del laboratorio, Simular un PDA: buscar entre configuraciones y El código de la semana. Opcional (✂️): Cómo trabaja un parser real, y las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, sec. 2.2 (Pushdown Automata) para la sesión A y sec. 2.3 (Non-Context-Free Languages) para la sesión B. Para la parte opcional, sec. 2.4 (Deterministic Context-Free Languages), solo como consulta. Son apoyo: estos apuntes se pueden estudiar solos.

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

Un autómata finito con una pila

Un autómata finito no reconoce { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} porque no tiene dónde anotar cuántos ceros leyó: su única memoria es el estado, y los estados son una cantidad fija. La solución más simple que se le ocurre a cualquiera que programe es darle una pila (stack).

Una pila es la estructura que conocen de Estructuras de Datos, y aquí se usa con sus dos operaciones de siempre: poner un símbolo encima y sacar el que está encima. Tiene dos propiedades que definen a la máquina.

  • No tiene límite de tamaño. Puede guardar tantos símbolos como haga falta. Eso es lo que el autómata finito no tenía.
  • Solo se ve la cima. Para mirar un símbolo que está más abajo hay que sacar los que tiene encima, y lo que se saca se pierde. Esto es lo que la máquina no puede hacer, y de ahí saldrá su límite en la sesión B.

Con una pila, reconocer 0n1n\mathtt{0}^n\mathtt{1}^n es directo:

1. Mientras lleguen ceros, poner cada uno en la pila.
2. Cuando llegue el primer 1, empezar a sacar: por cada 1 que se lee, sacar un 0.
3. Si se termina la entrada justo cuando la pila queda vacía, aceptar.
   Si sobra un 1 (no hay 0 que sacar), si sobran ceros en la pila, o si aparece un 0
   después de un 1, rechazar.

El paso 3 esconde un problema: la máquina solo ve la cima, y no puede ver que la pila está vacía. Sacar de una pila vacía no es una operación que “falla y avisa”: simplemente no se puede hacer. La solución es un truco que usaremos en casi todos los autómatas del capítulo. Antes de leer nada, la máquina pone en la pila un símbolo especial, que escribiremos $. Cuando ese símbolo vuelve a estar en la cima, la máquina sabe que todo lo que puso después ya salió.

El autómata completo tiene cuatro estados. Cada flecha lleva una etiqueta con tres partes: lo que lee, lo que saca y, después de la flecha, lo que pone.

Diagrama de estados del autómata de pila de 0ⁿ1ⁿ, con cuatro estados en fila: q₀, que es el inicial y de aceptación, q₁, q₂ y q₃, también de aceptación. De q₀ a q₁ hay una flecha con la etiqueta ε, ε → $. q₁ tiene un bucle con 0, ε → 0. De q₁ a q₂, una flecha con 1, 0 → ε. q₂ tiene un bucle con 1, 0 → ε. De q₂ a q₃, una flecha con ε, $ → ε. Debajo de cada estado, lo que hace la máquina ahí: al salir de q₀ pone $, la marca del fondo; en q₁ guarda, pone un 0 por cada 0 que lee; en q₂ compara, saca un 0 por cada 1 que lee; a q₃ llega solo si la cima es $, cuando no quedan ceros. Abajo, cómo se lee la etiqueta 1, 0 → ε: lee el siguiente símbolo de la entrada, saca ese símbolo, que debe estar en la cima, y pone un símbolo encima, que aquí es ε, nadaDiagrama de estados del autómata de pila de 0ⁿ1ⁿ, con cuatro estados en fila: q₀, que es el inicial y de aceptación, q₁, q₂ y q₃, también de aceptación. De q₀ a q₁ hay una flecha con la etiqueta ε, ε → $. q₁ tiene un bucle con 0, ε → 0. De q₁ a q₂, una flecha con 1, 0 → ε. q₂ tiene un bucle con 1, 0 → ε. De q₂ a q₃, una flecha con ε, $ → ε. Debajo de cada estado, lo que hace la máquina ahí: al salir de q₀ pone $, la marca del fondo; en q₁ guarda, pone un 0 por cada 0 que lee; en q₂ compara, saca un 0 por cada 1 que lee; a q₃ llega solo si la cima es $, cuando no quedan ceros. Abajo, cómo se lee la etiqueta 1, 0 → ε: lee el siguiente símbolo de la entrada, saca ese símbolo, que debe estar en la cima, y pone un símbolo encima, que aquí es ε, nada
El autómata de pila de 0ⁿ1ⁿ. Cada etiqueta dice qué lee, qué saca y, después de la flecha, qué pone; con ε en un lugar, esa parte no se hace.
  • De q0q_0 a q1q_1: sin leer nada y sin sacar nada, pone $. Es la marca del fondo.
  • En q1q_1: lee un 0\mathtt{0} y lo pone en la pila.
  • De q1q_1 a q2q_2, y en q2q_2: lee un 1\mathtt{1} y saca un 0\mathtt{0}.
  • De q2q_2 a q3q_3: sin leer nada, saca $. Solo puede hacerlo si $ está en la cima, es decir, si ya salieron todos los ceros.

Los estados de aceptación son q0q_0, para aceptar la cadena vacía, y q3q_3. El autómata está en el archivo machines/zeros_ones.pda, y el programa run_pda lo sigue con una cadena:

$ build/run_pda machines/zeros_ones.pda 0011 '' 001
w = 0011
  paso  transición  estado  falta leer  pila
     0              q0      0011        ε
     1  ε, ε → $    q1      0011        $
     2  0, ε → 0    q1      011         0$
     3  0, ε → 0    q1      11          00$
     4  1, 0 → ε    q2      1           0$
     5  1, 0 → ε    q2      ε           $
     6  ε, $ → ε    q3      ε           ε
  acepta en q3 (configuraciones exploradas: 7)
w = ε
  paso  transición  estado  falta leer  pila
     0              q0      ε           ε
  acepta en q0 (configuraciones exploradas: 1)
w = 001
  rechaza: 5 configuraciones alcanzables, ninguna acepta

Cada fila es un instante: el estado, lo que falta leer de la entrada y el contenido de la pila, con la cima a la izquierda. En la fila 3 la pila es 00$: dos ceros encima de la marca. En las filas 4 y 5 cada 1\mathtt{1} se lleva un cero. En la fila 5 la cima es $, y eso permite el último paso.

Animación del autómata de pila de 0ⁿ1ⁿ leyendo 0011. Arriba está la entrada en celdas, con una marca que avanza; en el medio, el diagrama de estados, con el estado actual resaltado y una ficha que recorre cada transición; a la derecha, la pila dibujada de pie, con la cima arriba; y debajo, la configuración. Al comienzo: estado q₀, toda la entrada por leer y la pila vacía, configuración (q₀, 0011, ε). Paso 1: sin leer nada pasa a q₁ y pone $, la marca del fondo: (q₁, 0011, $). Paso 2: lee un 0 por el bucle de q₁ y lo pone en la pila: (q₁, 011, 0$). Paso 3: lee el otro 0 y lo pone encima: (q₁, 11, 00$). Paso 4: lee el primer 1, saca un 0 y pasa a q₂: (q₂, 1, 0$). Paso 5: lee el segundo 1 por el bucle de q₂ y saca el otro 0; la cima vuelve a ser $: (q₂, ε, $). Paso 6: sin leer nada saca $ y pasa a q₃, con la pila vacía y sin nada por leer: (q₃, ε, ε), y aceptaAnimación del autómata de pila de 0ⁿ1ⁿ leyendo 0011. Arriba está la entrada en celdas, con una marca que avanza; en el medio, el diagrama de estados, con el estado actual resaltado y una ficha que recorre cada transición; a la derecha, la pila dibujada de pie, con la cima arriba; y debajo, la configuración. Al comienzo: estado q₀, toda la entrada por leer y la pila vacía, configuración (q₀, 0011, ε). Paso 1: sin leer nada pasa a q₁ y pone $, la marca del fondo: (q₁, 0011, $). Paso 2: lee un 0 por el bucle de q₁ y lo pone en la pila: (q₁, 011, 0$). Paso 3: lee el otro 0 y lo pone encima: (q₁, 11, 00$). Paso 4: lee el primer 1, saca un 0 y pasa a q₂: (q₂, 1, 0$). Paso 5: lee el segundo 1 por el bucle de q₂ y saca el otro 0; la cima vuelve a ser $: (q₂, ε, $). Paso 6: sin leer nada saca $ y pasa a q₃, con la pila vacía y sin nada por leer: (q₃, ε, ε), y acepta
Las siete filas de run_pda, una por una. La pila sube con cada 0 y baja con cada 1, y la marca $ es lo que le deja ver a la máquina que ya salieron todos.

Con 001\mathtt{001} la máquina rechaza. Después de leer todo queda en q2q_2 con la pila 0$: la cima es un 0\mathtt{0}, la transición a q3q_3 pide un $, y no hay otra. Qué quiere decir exactamente “configuraciones alcanzables” se precisa dos secciones más abajo.

Idea clave. Un autómata de pila es un autómata finito con una pila. Los estados siguen siendo una cantidad fija; la pila no tiene límite, pero solo se puede mirar y cambiar por la cima. En cada paso la máquina decide con tres datos: el estado, el siguiente símbolo de la entrada y la cima de la pila.

El autómata de arriba nunca tuvo que elegir. Los que vienen sí: un PDA es, por definición, no determinista, como un NFA. Puede tener varias transiciones posibles en un mismo instante, y transiciones que no leen nada. La razón no es comodidad, como en la semana 2: veremos que aquí el no determinismo no se puede quitar.

La definición formal de un PDA

Una transición de un PDA mira tres cosas y produce dos. Mira el estado, un símbolo de la entrada y un símbolo de la cima de la pila. Produce un estado nuevo y un símbolo para poner en la pila. Cualquiera de los símbolos puede faltar: la transición puede no leer, no sacar o no poner. Para escribir eso se usa una notación que aparece en toda la definición: si Σ\Sigma es un alfabeto,

Σε=Σ∪{ε}\Sigma_\varepsilon = \Sigma \cup \{\varepsilon\}

es el conjunto de sus símbolos más la opción “ninguno”.

Definición. Un autómata de pila (pushdown automaton), o PDA, es una séxtupla P=(Q,Σ,Γ,δ,q0,F)P = (Q, \Sigma, \Gamma, \delta, q_0, F), donde:

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

Es la definición de un NFA de la semana 2 con dos agregados: el alfabeto Γ\Gamma, y una coordenada más en la entrada y en la salida de δ\delta. Conviene leer con cuidado qué dice δ\delta.

  • (r,c)∈δ(q,a,b)(r, c) \in \delta(q, a, b) se lee: en el estado qq, leyendo aa y sacando bb de la cima, la máquina puede pasar al estado rr poniendo cc. En los diagramas, es una flecha de qq a rr con la etiqueta a,b→ca, b \to c.
  • a=εa = \varepsilon: la transición no lee nada de la entrada. b=εb = \varepsilon: no saca nada, y se puede usar con cualquier cosa en la cima, también con la pila vacía. c=εc = \varepsilon: no pone nada.
  • Los cuatro casos de bb y cc tienen nombre de operación: ε→c\varepsilon \to c pone cc; b→εb \to \varepsilon saca bb; b→cb \to c reemplaza la cima bb por cc; y ε→ε\varepsilon \to \varepsilon no toca la pila.
  • El resultado es un conjunto, como en un NFA. Puede tener varios elementos, y entonces la máquina elige. Puede ser vacío, y entonces ese camino no sigue.
  • Γ\Gamma y Σ\Sigma son alfabetos distintos, que pueden compartir símbolos o no. En el ejemplo anterior Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\} y Γ\Gamma tiene el 0\mathtt{0} y la marca $. La marca no está en Σ\Sigma: nunca aparece en la entrada.
  • Una transición pone a lo sumo un símbolo. Para poner dos hacen falta dos transiciones seguidas, con un estado intermedio. Lo necesitaremos en la construcción de la sección De gramática a PDA.

En el formato del curso, descrito en code/formats.md, la séxtupla es un archivo con un campo por componente. Este es machines/zeros_ones.pda:

# { 0^n 1^n : n >= 0 }
states: q0 q1 q2 q3
alphabet: 0 1
stack: 0 $
start: q0
accept: q0 q3
delta:
q0 eps eps -> q1 $
q1 0 eps -> q1 0
q1 1 0 -> q2 eps
q2 1 0 -> q2 eps
q2 eps $ -> q3 eps

Después de delta: va una transición por línea: estado lee saca -> destino pone, con eps donde va ε\varepsilon. La línea q1 1 0 -> q2 eps dice que (q2,ε)∈δ(q1,1,0)(q_2, \varepsilon) \in \delta(q_1, \mathtt{1}, \mathtt{0}). Dos líneas pueden tener el mismo lado izquierdo: así se escribe un conjunto con dos elementos. El programa show_pda muestra un archivo como séxtupla, listando solo los valores de δ\delta que no son vacíos. Con el autómata de los palíndromos, que veremos enseguida:

$ build/show_pda machines/even_palindromes.pda
Q  = {q0, q1, q2, q3}
Σ  = {0, 1}
Γ  = {0, 1, $}
q0 = q0
F  = {q3}

δ(q0, ε, ε) = {(q1, $)}
δ(q1, ε, ε) = {(q2, ε)}
δ(q1, 0, ε) = {(q1, 0)}
δ(q1, 1, ε) = {(q1, 1)}
δ(q2, ε, $) = {(q3, ε)}
δ(q2, 0, 0) = {(q2, ε)}
δ(q2, 1, 1) = {(q2, ε)}

4 estados, 7 transiciones

La función δ\delta completa tiene ∣Q∣⋅(∣Σ∣+1)⋅(∣Γ∣+1)=4⋅3⋅4=48|Q| \cdot (|\Sigma| + 1) \cdot (|\Gamma| + 1) = 4 \cdot 3 \cdot 4 = 48 valores. Siete son conjuntos de un elemento, y los otros 41 son ∅\emptyset.

En C++. El struct Pda de pda.h tiene los seis componentes con los nombres del formato: states, alphabet, stack, delta, start y accept. La función δ\delta es un std::map cuya clave es la terna (estado, lee, saca) y cuyo valor es un std::vector<Move>, la lista de pares (destino, pone). Una clave que no está en el mapa es un valor ∅\emptyset de δ\delta. El símbolo ε\varepsilon se guarda como el carácter '\0', con el nombre EPS: ningún símbolo de un archivo puede valer eso.

Error común. Escribir una transición que pone dos símbolos, como q1 a eps -> q1 x x. El formato y la definición permiten uno solo. El archivo errors/two_symbols.pda tiene esa línea, y run_pda lo rechaza al leerlo. Para poner xx se pasa por un estado intermedio: q1 a eps -> m x y m eps eps -> q1 x.

Configuraciones y el lenguaje de un PDA

En un DFA bastaba decir en qué estado estaba la máquina. En un PDA, para saber qué puede pasar después hacen falta tres datos, los tres que mostraba cada fila de run_pda.

Definición. Una configuración (configuration) de PP es una terna (q,x,γ)(q, x, \gamma), donde q∈Qq \in Q es el estado, x∈Σ∗x \in \Sigma^* es lo que falta leer de la entrada, y γ∈Γ∗\gamma \in \Gamma^* es el contenido de la pila, con la cima a la izquierda. La configuración inicial con la entrada ww es (q0,w,ε)(q_0, w, \varepsilon): nada leído, la pila vacía.

Un paso de la máquina lleva de una configuración a otra. Lo escribimos con el símbolo ⊢\vdash.

Definición. PP pasa en un paso de (q,ax,bγ)(q, ax, b\gamma) a (r,x,cγ)(r, x, c\gamma), y se escribe

(q,ax,bγ)⊢(r,x,cγ),(q, ax, b\gamma) \vdash (r, x, c\gamma),

si (r,c)∈δ(q,a,b)(r, c) \in \delta(q, a, b), donde a∈Σεa \in \Sigma_\varepsilon, b,c∈Γεb, c \in \Gamma_\varepsilon, x∈Σ∗x \in \Sigma^* y γ∈Γ∗\gamma \in \Gamma^*. Se escribe C⊢∗C′C \vdash^* C' si se llega de CC a C′C' en cero o más pasos.

La definición dice con símbolos lo que ya hicimos a mano. Si aa es un símbolo, es el primero de lo que falta leer, y desaparece. Si bb es un símbolo, es la cima, y se reemplaza por cc. El resto de la pila, γ\gamma, no cambia y ni siquiera se mira. Una secuencia C0⊢C1⊢⋯⊢CnC_0 \vdash C_1 \vdash \cdots \vdash C_n se llama una ejecución de PP.

Definición. PP acepta la cadena ww si

(q0,w,ε)⊢∗(q,ε,γ)para alguˊn q∈F y alguna γ∈Γ∗.(q_0, w, \varepsilon) \vdash^* (q, \varepsilon, \gamma) \quad \text{para algún } q \in F \text{ y alguna } \gamma \in \Gamma^*.

El lenguaje de PP es L(P)={ w∈Σ∗:P acepta w }L(P) = \{\, w \in \Sigma^* : P \text{ acepta } w \,\}, y se dice que PP reconoce L(P)L(P).

Una configuración (q,ε,γ)(q, \varepsilon, \gamma) con q∈Fq \in F se llama de aceptación. Hay cuatro cosas en esta definición que conviene dejar claras.

  • Basta una ejecución. Como en un NFA, la máquina acepta si alguna secuencia de elecciones termina bien. Que otras se queden sin transiciones o terminen en un estado que no es de aceptación no importa.
  • Hay que leer toda la entrada. La segunda coordenada debe ser ε\varepsilon. Pasar por un estado de aceptación cuando todavía falta leer no cuenta.
  • La pila puede quedar con cualquier cosa. Se acepta por estado. Vaciar la pila antes de aceptar es una costumbre útil, y la marca $ sirve para eso, pero la definición no lo pide.
  • Un camino puede morir. Si desde una configuración ninguna transición se puede usar, esa ejecución termina ahí. Pasa, por ejemplo, cuando la transición pide sacar un símbolo y la cima es otro, o la pila está vacía.

Con w=0011w = \mathtt{0011} y el autómata de la sección anterior, la ejecución que imprimió run_pda es, en esta notación (aquí el símbolo $ se ve como $\texttt{\textdollar}):

(q0,0011,ε)⊢(q1,0011,$)⊢(q1,011,0$)⊢(q1,11,00$)⊢(q2,1,0$)⊢(q2,ε,$)⊢(q3,ε,ε)\begin{aligned} (q_0, \mathtt{0011}, \varepsilon) &\vdash (q_1, \mathtt{0011}, \texttt{\textdollar}) \vdash (q_1, \mathtt{011}, \mathtt{0}\texttt{\textdollar}) \vdash (q_1, \mathtt{11}, \mathtt{00}\texttt{\textdollar}) \\ &\vdash (q_2, \mathtt{1}, \mathtt{0}\texttt{\textdollar}) \vdash (q_2, \varepsilon, \texttt{\textdollar}) \vdash (q_3, \varepsilon, \varepsilon) \end{aligned}

La última configuración es de aceptación: no falta leer nada y q3∈Fq_3 \in F.

Error común. Decir que el autómata acepta 00110\mathtt{00110} porque “llega a q3q_3”. Llega, después de leer 0011\mathtt{0011}, pero en la configuración (q3,0,ε)(q_3, \mathtt{0}, \varepsilon) todavía falta leer un símbolo, y q3q_3 no tiene transiciones. Ese camino muere sin aceptar, y no hay otro.

Sipser define la aceptación con una secuencia de estados r0,…,rmr_0, \ldots, r_m y una secuencia de pilas s0,…,sms_0, \ldots, s_m. Es la misma definición: (ri,si)(r_i, s_i) son la primera y la tercera coordenada de nuestras configuraciones, y la segunda se deduce de cuánto se leyó.

De la definición de ⊢\vdash sale una propiedad que usaremos en las dos demostraciones grandes del capítulo. Un paso solo mira la cima de la pila y el primer símbolo que falta leer. Lo que está más abajo en la pila, y lo que viene después en la entrada, no participa.

Lema (del fondo). Si (q,x,α)⊢∗(r,y,β)(q, x, \alpha) \vdash^* (r, y, \beta), entonces para toda z∈Σ∗z \in \Sigma^* y toda γ∈Γ∗\gamma \in \Gamma^*:

(q,xz,αγ)⊢∗(r,yz,βγ).(q, xz, \alpha\gamma) \vdash^* (r, yz, \beta\gamma).

Demostración. Por inducción sobre la cantidad de pasos. Con cero pasos las dos configuraciones son iguales y no hay nada que probar. Para un paso: si (q,ax′,bα′)⊢(r,x′,cα′)(q, ax', b\alpha') \vdash (r, x', c\alpha') porque (r,c)∈δ(q,a,b)(r, c) \in \delta(q, a, b), la misma transición da (q,ax′z,bα′γ)⊢(r,x′z,cα′γ)(q, ax'z, b\alpha'\gamma) \vdash (r, x'z, c\alpha'\gamma), porque la definición de ⊢\vdash permite cualquier cadena después de aa y cualquier pila debajo de bb. Una ejecución de n+1n + 1 pasos es una de nn seguida de un paso, y a cada parte se le agregan zz y γ\gamma igual. ∎

Dicho de otro modo: toda ejecución se puede repetir “más arriba”, encima de una pila que ya tenía cosas, y con más entrada esperando detrás. El recíproco no vale sin condiciones. Una ejecución que en algún momento saca un símbolo de γ\gamma no se puede repetir sin γ\gamma.

Diseñar un PDA

Diseñar un autómata finito era decidir qué recordar en el estado. Diseñar un PDA es repartir la memoria en dos: qué va en el estado, que es poco y siempre está a la vista, y qué va en la pila, que puede ser mucho pero solo se recupera en orden inverso al que se guardó. Casi todos los diseños siguen el mismo plan:

  1. marcar el fondo de la pila;
  2. una fase que guarda, una fase que saca y compara;
  3. el estado recuerda en qué fase está la máquina;
  4. al final, comprobar que la pila volvió a la marca.

Marcar el fondo de la pila

La marca $ ya apareció, y vale la pena decir por qué es necesaria. La función δ\delta recibe un símbolo de Γε\Gamma_\varepsilon como tercera coordenada. Con un símbolo bb, la transición exige que bb esté en la cima. Con ε\varepsilon, no exige nada. No existe una tercera coordenada que diga “la pila está vacía”. Una transición con ε\varepsilon se puede usar con la pila vacía y también con la pila llena.

La marca convierte “la pila está vacía” en algo que sí se puede preguntar: “la cima es $”. Sin ella, el autómata de 0n1n\mathtt{0}^n\mathtt{1}^n no podría distinguir 0011\mathtt{0011} de 00011\mathtt{00011}. Con la segunda quedaría en q2q_2 con un cero en la pila, y si la transición a q3q_3 fuera ε,ε→ε\varepsilon, \varepsilon \to \varepsilon, la tomaría igual.

Hay autómatas que no la necesitan. El del lenguaje { aibj:i≥j }\{\, \mathtt{a}^i\mathtt{b}^j : i \geq j \,\} pone una a\mathtt{a} por cada a\mathtt{a}, saca una por cada b\mathtt{b} y acepta en cualquier momento, sobre lo que sobre: le alcanza con que una b\mathtt{b} de más no encuentre nada que sacar y ese camino muera. Es uno de los casos del laboratorio.

Paréntesis balanceados

El lenguaje de los paréntesis balanceados, con la gramática S→(S)S∣εS \to \mathtt{(}S\mathtt{)}S \mid \varepsilon de la semana 5, es el ejemplo natural de una pila: es lo que hace cualquier editor de código para emparejar paréntesis. Cada paréntesis que abre se guarda, y cada uno que cierra saca uno guardado.

Estado Lee, saca →\to pone Destino Para qué
q0q_0 ε,ε→$\varepsilon, \varepsilon \to \texttt{\textdollar} q1q_1 marcar el fondo
q1q_1 (,ε→(\mathtt{(}, \varepsilon \to \mathtt{(} q1q_1 abrir: guardar
q1q_1 ),(→ε\mathtt{)}, \mathtt{(} \to \varepsilon q1q_1 cerrar: tiene que haber uno abierto
q1q_1 ε,$→ε\varepsilon, \texttt{\textdollar} \to \varepsilon q2q_2 no queda nada abierto

El único estado de aceptación es q2q_2. A diferencia del autómata de 0n1n\mathtt{0}^n\mathtt{1}^n, aquí hay un solo estado de trabajo: guardar y sacar se alternan, y no hay fases que recordar.

$ build/run_pda machines/balanced.pda '(())()' '())'
w = (())()
  paso  transición  estado  falta leer  pila
     0              q0      (())()      ε
     1  ε, ε → $    q1      (())()      $
     2  (, ε → (    q1      ())()       ($
     3  (, ε → (    q1      ))()        (($
     4  ), ( → ε    q1      )()         ($
     5  ), ( → ε    q1      ()          $
     6  (, ε → (    q1      )           ($
     7  ), ( → ε    q1      ε           $
     8  ε, $ → ε    q2      ε           ε
  acepta en q2 (configuraciones exploradas: 11)
w = ())
  rechaza: 6 configuraciones alcanzables, ninguna acepta

La altura de la pila en cada fila es la cantidad de paréntesis abiertos sin cerrar. En la fila 5 la cima es $: el prefijo (()) está balanceado. Cada vez que la cima es $, como en las filas 1 y 5, el autómata puede pasar a q2q_2, y ahí tiene una elección. Si pasa en la fila 5, queda en q2q_2 con () por leer y sin transiciones, y ese camino muere. La ejecución que acepta es la que sigue en q1q_1 y deja el salto para el final. Con ()), el tercer símbolo pide sacar un ( y la cima es $: no hay camino.

Palíndromos de longitud par: adivinar el medio

Sea B={ wwR:w∈{0,1}∗ }B = \{\, ww^R : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\}, los palíndromos de longitud par: 0110\mathtt{0110}, 1001\mathtt{1001}, 00\mathtt{00}, ε\varepsilon. La gramática es S→0S0∣1S1∣εS \to \mathtt{0}S\mathtt{0} \mid \mathtt{1}S\mathtt{1} \mid \varepsilon.

El plan es el de siempre: guardar la primera mitad, y después sacar comparando con la segunda. Una pila devuelve lo guardado en orden inverso, que es justo lo que hace falta para comparar ww con wRw^R. El problema es otro: ¿cuándo termina la primera mitad? En 0n1n\mathtt{0}^n\mathtt{1}^n lo avisaba el primer 1\mathtt{1}. Aquí no hay ninguna señal en la entrada, y la máquina no sabe cuánto mide la cadena.

La respuesta es la del no determinismo: no lo sabe, así que lo adivina. En q1q_1 guarda. En cualquier momento, sin leer nada, puede pasar a q2q_2, y desde ahí solo saca y compara.

Estado Lee, saca →\to pone Destino Para qué
q0q_0 ε,ε→$\varepsilon, \varepsilon \to \texttt{\textdollar} q1q_1 marcar el fondo
q1q_1 0,ε→0\mathtt{0}, \varepsilon \to \mathtt{0} y 1,ε→1\mathtt{1}, \varepsilon \to \mathtt{1} q1q_1 primera mitad: guardar lo que se lee
q1q_1 ε,ε→ε\varepsilon, \varepsilon \to \varepsilon q2q_2 adivinar que aquí está el medio
q2q_2 0,0→ε\mathtt{0}, \mathtt{0} \to \varepsilon y 1,1→ε\mathtt{1}, \mathtt{1} \to \varepsilon q2q_2 segunda mitad: lo leído debe ser igual a la cima
q2q_2 ε,$→ε\varepsilon, \texttt{\textdollar} \to \varepsilon q3q_3 se comparó todo
$ build/run_pda machines/even_palindromes.pda 0110 011
w = 0110
  paso  transición  estado  falta leer  pila
     0              q0      0110        ε
     1  ε, ε → $    q1      0110        $
     2  0, ε → 0    q1      110         0$
     3  1, ε → 1    q1      10          10$
     4  ε, ε → ε    q2      10          10$
     5  1, 1 → ε    q2      0           0$
     6  0, 0 → ε    q2      ε           $
     7  ε, $ → ε    q3      ε           ε
  acepta en q3 (configuraciones exploradas: 15)
w = 011
  rechaza: 11 configuraciones alcanzables, ninguna acepta

En el paso 4 la máquina adivina, después de leer exactamente dos símbolos. Esa es la ejecución que run_pda muestra, pero para encontrarla exploró 15 configuraciones: también probó saltar a q2q_2 en los otros momentos posibles, antes de leer nada y después de uno, de tres y de cuatro símbolos. Esos intentos mueren. Por ejemplo, si salta después de un símbolo queda en (q2,110,0$)(q_2, \mathtt{110}, \mathtt{0}\texttt{\textdollar}), lee un 1\mathtt{1} con un 0\mathtt{0} en la cima, y no hay transición.

“Adivinar” no es magia ni suerte. Quiere decir, como en la semana 2, que la definición de aceptar pide que exista una ejecución buena. Si la cadena es wwRww^R, la ejecución que salta en el medio existe y acepta. Si la cadena no es de esa forma, ningún punto de salto sirve, y eso es lo que hay que comprobar al demostrar que el autómata es correcto: que una ejecución que acepta solo puede haber saltado en el medio de un palíndromo.

Idea clave. En un PDA, el no determinismo sirve para tomar una decisión que depende de algo que todavía no se leyó: dónde está el medio, cuál de dos comparaciones hacer. La máquina acepta si alguna de las decisiones posibles lleva a aceptar.

Elegir qué comparar

El último ejemplo usa el no determinismo de otra manera. Sea

C={ aibjck:i=j o j=k }.C = \{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i = j \text{ o } j = k \,\}.

Una cadena está en CC por dos razones posibles, y el autómata no sabe cuál hasta haber leído todo. Así que al empezar, sin leer nada, elige una de dos ramas. La primera compara las a\mathtt{a} con las b\mathtt{b} y deja pasar las c\mathtt{c} sin mirar. La segunda deja pasar las a\mathtt{a} y compara las b\mathtt{b} con las c\mathtt{c}. Cada rama es un autómata como el de 0n1n\mathtt{0}^n\mathtt{1}^n. El archivo es machines/ij_or_jk.pda, con nueve estados:

$ build/run_pda machines/ij_or_jk.pda abbcc
w = abbcc
  paso  transición  estado  falta leer  pila
     0              q0      abbcc       ε
     1  ε, ε → $    q1      abbcc       $
     2  ε, ε → ε    q5      abbcc       $
     3  a, ε → ε    q5      bbcc        $
     4  ε, ε → ε    q6      bbcc        $
     5  b, ε → b    q6      bcc         b$
     6  b, ε → b    q6      cc          bb$
     7  ε, ε → ε    q7      cc          bb$
     8  c, b → ε    q7      c           b$
     9  c, b → ε    q7      ε           $
    10  ε, $ → ε    q8      ε           ε
  acepta en q8 (configuraciones exploradas: 24)

En el paso 2 elige la segunda rama, la de j=kj = k. En el paso 3 lee la a\mathtt{a} sin tocar la pila. Con aabbc\mathtt{aabbc} acepta por la primera rama, y con abc\mathtt{abc} por cualquiera de las dos.

La construcción es general: dados dos PDA, uno nuevo que al empezar salta sin leer nada al inicio de uno o del otro reconoce la unión de sus lenguajes. Es la misma idea que la unión de dos NFA.

Error común. Usar la pila como un contador de dos cosas a la vez. Aquí las dos comparaciones están en ramas separadas, y cada ejecución hace una sola. Un autómata que intentara comprobar i=ji = j y j=kj = k en la misma ejecución tendría que guardar las a\mathtt{a}, sacarlas con las b\mathtt{b}, y al llegar a las c\mathtt{c} ya no tendría con qué comparar: la pila se gastó. Una pila compara una sola pareja de cantidades. La sesión B demuestra que esto no es falta de ingenio, sino un límite de la máquina.

Simular un PDA: buscar entre configuraciones

El programa run_pda no “adivina”: prueba. Vale la pena ver cómo, porque es el problema del laboratorio y porque muestra en qué se diferencia simular un PDA de simular un NFA.

Para un NFA, en la semana 2, bastaba llevar el conjunto de estados en los que la máquina podía estar después de cada símbolo. Era un conjunto finito, de a lo sumo ∣Q∣|Q| elementos, y avanzaba un símbolo por vez. Con un PDA eso no alcanza: dos ejecuciones que están en el mismo estado pueden tener pilas distintas, y lo que hagan después depende de la pila. Lo que hay que llevar es el conjunto de configuraciones.

Las configuraciones forman un grafo: hay una arista de CC a C′C' si C⊢C′C \vdash C'. El PDA acepta ww si y solo si desde la configuración inicial (q0,w,ε)(q_0, w, \varepsilon) se alcanza alguna configuración de aceptación. Simular es recorrer ese grafo, con la búsqueda por niveles o en profundidad que conocen de Algoritmos.

algoritmo simular(P, w, límite)
    inicial ← (q0, 0, pila vacía)
    vistas ← {inicial}
    pendientes ← cola con inicial
    mientras pendientes no esté vacía
        C ← sacar de pendientes
        si C tiene toda la entrada leída y su estado está en F entonces
            devolver ACEPTA
        fin si
        para cada C' tal que C ⊢ C'
            si C' no está en vistas entonces
                agregar C' a vistas y a pendientes
                si vistas tiene más de límite configuraciones entonces
                    devolver LÍMITE
                fin si
            fin si
        fin para
    fin mientras
    devolver RECHAZA
fin algoritmo

En el código, la segunda coordenada de la configuración es la posición en la entrada, cuántos símbolos se leyeron, en lugar de la cadena que falta. Es la misma información y ocupa menos. La función simulate de pda.h es este algoritmo, con un detalle: comprueba la aceptación al descubrir una configuración y no al sacarla de la cola, que da el mismo resultado un poco antes.

El algoritmo tiene tres finales, y cada uno responde a un problema distinto.

El conjunto de vistas hace que la búsqueda termine. Un PDA puede tener un ciclo de transiciones ε\varepsilon que no cambia la pila: de pp a qq y de qq a pp, las dos con ε,ε→ε\varepsilon, \varepsilon \to \varepsilon. Una búsqueda que no recuerde por dónde pasó daría vueltas ahí para siempre. Con el conjunto, la segunda vez que llega a una configuración la descarta. Además evita trabajo repetido: cuando dos caminos distintos llegan a la misma configuración, lo que sigue es igual para los dos, y se explora una sola vez.

Si las configuraciones se acaban, la respuesta es definitiva. Cuando la cola queda vacía se recorrieron todas las configuraciones alcanzables y ninguna era de aceptación: la máquina rechaza. Eso es lo que decía run_pda con 001: “5 configuraciones alcanzables, ninguna acepta”.

Pero las configuraciones pueden no acabarse. Los estados son finitos y las posiciones también, pero las pilas no. Un PDA con la transición q eps eps -> q x, un ciclo de transiciones ε\varepsilon que hace crecer la pila, tiene desde qq infinitas configuraciones alcanzables: una por cada altura. Ninguna búsqueda las recorre todas. Por eso el algoritmo recibe un límite y tiene una tercera respuesta, que no es “acepta” ni “rechaza” sino “no lo sé con este presupuesto”.

Ese tercer final no es un caso raro inventado para molestar. Aparece con el autómata más natural de la sección siguiente, y volveremos a él ahí.

En C++. En pda.h, una configuración es un struct Config con el estado, la posición y la pila como un std::string con la cima en stack[0]. Las vistas van en un std::set<Config>, que necesita comparar configuraciones: la línea auto operator<=>(const Config&) const = default; le pide al compilador la comparación campo por campo. Para poder mostrar la ejecución que acepta, cada configuración descubierta guarda desde cuál se llegó a ella, y al final se recorre esa cadena hacia atrás.

En la práctica. Buscar en un grafo de configuraciones con un conjunto de vistas es la base de las herramientas que verifican programas y protocolos: cada configuración es un estado posible del sistema, y la pregunta es si se alcanza uno malo. Cuando el programa tiene llamadas a funciones, su pila de llamadas hace que el modelo sea, literalmente, un autómata de pila.

De gramática a PDA

Ahora la primera mitad del teorema central de la semana: todo lo que una gramática libre de contexto genera, algún PDA lo reconoce. Es una construcción, y la hacemos completa.

Teorema. Para toda gramática libre de contexto GG existe un PDA PP con L(P)=L(G)L(P) = L(G).

La idea: la pila guarda lo que falta derivar

Una derivación por la izquierda, como las de la semana 5, reemplaza siempre la variable que está más a la izquierda. Con S→(S)S∣εS \to \mathtt{(}S\mathtt{)}S \mid \varepsilon:

S⇒(S)S⇒()S⇒()(S)S⇒()()S⇒()()S \Rightarrow \mathtt{(}S\mathtt{)}S \Rightarrow \mathtt{()}S \Rightarrow \mathtt{()(}S\mathtt{)}S \Rightarrow \mathtt{()()}S \Rightarrow \mathtt{()()}

En cada paso la cadena tiene dos partes: un prefijo de terminales, que ya no va a cambiar, y el resto, que empieza con la variable que toca reemplazar. El PDA va a seguir una derivación así, con una división del trabajo muy simple: el prefijo de terminales no lo guarda, lo compara con la entrada y lo olvida. El resto lo guarda en la pila, con su primer símbolo en la cima.

Entonces la máquina repite una de dos acciones, según lo que haya en la cima:

  • Si la cima es una variable AA: elige una regla A→uA \to u, saca AA y pone uu. Es un paso de la derivación. Aquí está el no determinismo: la máquina adivina qué regla usar.
  • Si la cima es un terminal aa: lo compara con el siguiente símbolo de la entrada. Si son iguales, lee uno y saca el otro. Si no, este camino muere: la derivación que venía adivinando no produce esta cadena.

Empieza con la variable inicial en la pila, encima de la marca $, y acepta cuando la pila vuelve a la marca con toda la entrada leída: no queda nada por derivar ni nada por leer.

Idea clave. En el PDA de una gramática, la pila contiene en cada instante lo que falta derivar: si ya se leyó xx y la pila es β\beta encima de la marca, entonces S⇒∗xβS \Rightarrow^* x\beta. El autómata no construye la cadena: adivina una derivación por la izquierda y comprueba que produce la entrada.

La construcción

Hay un detalle técnico. “Sacar AA y poner uu” pone varios símbolos de una vez, y una transición pone a lo sumo uno. Se resuelve con una fila de estados intermedios que ponen los símbolos de uu de uno en uno, de derecha a izquierda, para que el primero quede en la cima.

Qué se construye. Sea G=(V,Σ,R,S)G = (V, \Sigma, R, S). El PDA es P=(Q,Σ,Γ,δ,qstart,{qaccept})P = (Q, \Sigma, \Gamma, \delta, q_{\text{start}}, \{q_{\text{accept}}\}) con Γ=V∪Σ∪{$}\Gamma = V \cup \Sigma \cup \{\texttt{\textdollar}\}, donde $ es un símbolo que no está en VV ni en Σ\Sigma. Sus estados son qstartq_{\text{start}}, qbeginq_{\text{begin}}, qloopq_{\text{loop}} y qacceptq_{\text{accept}}, más los intermedios de cada regla. Las transiciones son:

  1. Preparar. qstartq_{\text{start}} pone $ y pasa a qbeginq_{\text{begin}}, que pone SS y pasa a qloopq_{\text{loop}}. Las dos sin leer nada.
  2. Reemplazar. Para cada regla A→X1X2⋯XkA \to X_1X_2 \cdots X_k de RR, donde cada XiX_i es una variable o un terminal:
    • si k=0k = 0, es decir, la regla es A→εA \to \varepsilon: en qloopq_{\text{loop}}, la transición ε,A→ε\varepsilon, A \to \varepsilon a qloopq_{\text{loop}};
    • si k=1k = 1: en qloopq_{\text{loop}}, la transición ε,A→X1\varepsilon, A \to X_1 a qloopq_{\text{loop}};
    • si k≥2k \geq 2: estados nuevos r1,…,rk−1r_1, \ldots, r_{k-1}, propios de esta regla, y las transiciones ε,A→Xk\varepsilon, A \to X_k de qloopq_{\text{loop}} a r1r_1; ε,ε→Xk−j\varepsilon, \varepsilon \to X_{k-j} de rjr_j a rj+1r_{j+1}, para j=1,…,k−2j = 1, \ldots, k - 2; y ε,ε→X1\varepsilon, \varepsilon \to X_1 de rk−1r_{k-1} a qloopq_{\text{loop}}.
  3. Comparar. Para cada terminal a∈Σa \in \Sigma: en qloopq_{\text{loop}}, la transición a,a→εa, a \to \varepsilon a qloopq_{\text{loop}}.
  4. Terminar. En qloopq_{\text{loop}}, la transición ε,$→ε\varepsilon, \texttt{\textdollar} \to \varepsilon a qacceptq_{\text{accept}}.

El PDA tiene 4+∑(k−1)4 + \sum (k - 1) estados, donde la suma es sobre las reglas con k≥2k \geq 2 símbolos a la derecha. Todo el trabajo pasa en qloopq_{\text{loop}}; los demás estados solo existen para poner símbolos de uno en uno.

Un ejemplo completo

El programa cfg_to_pda aplica la construcción a un archivo .cfg y escribe el .pda. Con la gramática de los paréntesis, machines/balanced.cfg, que tiene las reglas S→(S)SS \to \mathtt{(}S\mathtt{)}S y S→εS \to \varepsilon:

$ build/cfg_to_pda machines/balanced.cfg
# PDA de la gramática machines/balanced.cfg.
states: q_start q_begin q_loop q_accept r1_1 r1_2 r1_3
alphabet: ( )
stack: ( ) S $
start: q_start
accept: q_accept
delta:
q_start eps eps -> q_begin $
q_begin eps eps -> q_loop S
q_loop eps $ -> q_accept eps
q_loop eps S -> r1_1 S
q_loop eps S -> q_loop eps
q_loop ( ( -> q_loop eps
q_loop ) ) -> q_loop eps
r1_1 eps eps -> r1_2 )
r1_2 eps eps -> r1_3 S
r1_3 eps eps -> q_loop (

La regla 1, S→(S)SS \to \mathtt{(}S\mathtt{)}S, tiene k=4k = 4 símbolos a la derecha, así que usa tres estados intermedios, r1_1, r1_2 y r1_3. La línea q_loop eps S -> r1_1 S saca SS y pone el último símbolo de la regla, que también es una SS. Las tres siguientes ponen ), S y (, en ese orden: el paréntesis que abre queda en la cima. La regla 2, S→εS \to \varepsilon, es la línea q_loop eps S -> q_loop eps. En total, 4+3=74 + 3 = 7 estados y 10 transiciones.

Guardamos esa salida en un archivo y la seguimos con ()():

$ build/cfg_to_pda machines/balanced.cfg > build/balanced_from_cfg.pda
$ build/run_pda build/balanced_from_cfg.pda '()()'
w = ()()
  paso  transición  estado    falta leer  pila
     0              q_start   ()()        ε
     1  ε, ε → $    q_begin   ()()        $
     2  ε, ε → S    q_loop    ()()        S$
     3  ε, S → S    r1_1      ()()        S$
     4  ε, ε → )    r1_2      ()()        )S$
     5  ε, ε → S    r1_3      ()()        S)S$
     6  ε, ε → (    q_loop    ()()        (S)S$
     7  (, ( → ε    q_loop    )()         S)S$
     8  ε, S → ε    q_loop    )()         )S$
     9  ), ) → ε    q_loop    ()          S$
    10  ε, S → S    r1_1      ()          S$
    11  ε, ε → )    r1_2      ()          )S$
    12  ε, ε → S    r1_3      ()          S)S$
    13  ε, ε → (    q_loop    ()          (S)S$
    14  (, ( → ε    q_loop    )           S)S$
    15  ε, S → ε    q_loop    )           )S$
    16  ), ) → ε    q_loop    ε           S$
    17  ε, S → ε    q_loop    ε           $
    18  ε, $ → ε    q_accept  ε           ε
  acepta en q_accept (configuraciones exploradas: 33)

Miren solo las filas donde el estado es q_loop, y en cada una junten lo ya leído con la pila sin la marca:

Fila Ya leído Pila sin $ Juntos
2 ε\varepsilon SS SS
6 ε\varepsilon (S)S\mathtt{(}S\mathtt{)}S (S)S\mathtt{(}S\mathtt{)}S
7 (\mathtt{(} S)SS\mathtt{)}S (S)S\mathtt{(}S\mathtt{)}S
8 (\mathtt{(} )S\mathtt{)}S ()S\mathtt{()}S
9 ()\mathtt{()} SS ()S\mathtt{()}S
13 ()\mathtt{()} (S)S\mathtt{(}S\mathtt{)}S ()(S)S\mathtt{()(}S\mathtt{)}S
14 ()(\mathtt{()(} S)SS\mathtt{)}S ()(S)S\mathtt{()(}S\mathtt{)}S
15 ()(\mathtt{()(} )S\mathtt{)}S ()()S\mathtt{()()}S
16 ()()\mathtt{()()} SS ()()S\mathtt{()()}S
17 ()()\mathtt{()()} ε\varepsilon ()()\mathtt{()()}

La última columna, sin repeticiones, es la derivación por la izquierda del principio de la sección: S⇒(S)S⇒()S⇒()(S)S⇒()()S⇒()()S \Rightarrow \mathtt{(}S\mathtt{)}S \Rightarrow \mathtt{()}S \Rightarrow \mathtt{()(}S\mathtt{)}S \Rightarrow \mathtt{()()}S \Rightarrow \mathtt{()()}. Cuando la máquina reemplaza, la columna avanza un paso de la derivación. Cuando compara, un terminal pasa de la pila a lo ya leído y la columna no cambia.

Animación del PDA de la gramática S → (S)S | ε leyendo ()(), mostrando solo las visitas a q_loop. A la izquierda, la entrada con la marca de lectura y la pila de pie, con $ en el fondo; a la derecha, la derivación por la izquierda, que se escribe línea por línea, y debajo una fila de celdas con lo ya leído seguido de la pila. Fila 2: la pila es S sobre la marca y la forma es S. Fila 6, reemplazar con S → (S)S: sale S y entran ), S y ( sobre la S del final; la pila es (S)S y la derivación avanza a (S)S. Fila 7, comparar: lee ( y lo saca; leído (, pila S)S. Fila 8, reemplazar con S → ε: sale S; la derivación avanza a ()S. Fila 9, comparar: lee ) y lo saca; leído (), pila S. Fila 13, reemplazar con S → (S)S: la pila es (S)S y la derivación avanza a ()(S)S. Fila 14, comparar: leído ()(, pila S)S. Fila 15, reemplazar con S → ε: la derivación avanza a ()()S. Fila 16, comparar: leído ()(), pila S. Fila 17, reemplazar con S → ε: la pila queda en la marca y la derivación termina en ()(). Fila 18: saca $, pasa a q_accept y acepta. En todos los pasos, lo ya leído seguido de la pila es la forma resaltada de la derivaciónAnimación del PDA de la gramática S → (S)S | ε leyendo ()(), mostrando solo las visitas a q_loop. A la izquierda, la entrada con la marca de lectura y la pila de pie, con $ en el fondo; a la derecha, la derivación por la izquierda, que se escribe línea por línea, y debajo una fila de celdas con lo ya leído seguido de la pila. Fila 2: la pila es S sobre la marca y la forma es S. Fila 6, reemplazar con S → (S)S: sale S y entran ), S y ( sobre la S del final; la pila es (S)S y la derivación avanza a (S)S. Fila 7, comparar: lee ( y lo saca; leído (, pila S)S. Fila 8, reemplazar con S → ε: sale S; la derivación avanza a ()S. Fila 9, comparar: lee ) y lo saca; leído (), pila S. Fila 13, reemplazar con S → (S)S: la pila es (S)S y la derivación avanza a ()(S)S. Fila 14, comparar: leído ()(, pila S)S. Fila 15, reemplazar con S → ε: la derivación avanza a ()()S. Fila 16, comparar: leído ()(), pila S. Fila 17, reemplazar con S → ε: la pila queda en la marca y la derivación termina en ()(). Fila 18: saca $, pasa a q_accept y acepta. En todos los pasos, lo ya leído seguido de la pila es la forma resaltada de la derivación
La tabla anterior, en movimiento. Reemplazar cambia la pila y hace avanzar la derivación; comparar pasa un terminal de la pila a lo ya leído, y la forma queda igual.

Por qué funciona

Hay que demostrar L(P)=L(G)L(P) = L(G), en las dos direcciones. Las dos son inducciones, y las dos dicen lo mismo que la tabla: lo leído seguido de la pila es siempre una cadena que la gramática deriva.

Usaremos dos hechos sobre derivaciones que se ven en el árbol de derivación de la semana 5. Primero: si S⇒∗wS \Rightarrow^* w, entonces ww tiene una derivación por la izquierda. Segundo: los terminales no se reemplazan nunca, así que si xα⇒∗wx\alpha \Rightarrow^* w con x∈Σ∗x \in \Sigma^*, entonces w=xw′w = xw' y α⇒∗w′\alpha \Rightarrow^* w' con los mismos pasos.

En lo que sigue, α\alpha, β\beta y η\eta son cadenas de variables y terminales, es decir, de (V∪Σ)∗(V \cup \Sigma)^*, y γ\gamma es cualquier contenido de pila.

Afirmación 1 (lo que la gramática deriva, el PDA lo consume). Si α\alpha tiene una derivación por la izquierda de nn pasos hasta una cadena de terminales ww, entonces para toda y∈Σ∗y \in \Sigma^* y toda γ\gamma:

(qloop,wy,αγ)⊢∗(qloop,y,γ).(q_{\text{loop}}, wy, \alpha\gamma) \vdash^* (q_{\text{loop}}, y, \gamma).

En palabras: con α\alpha en la cima, el PDA puede leer ww y dejar la pila como estaba debajo de α\alpha.

Demostración. Por inducción sobre nn.

Caso base: n=0n = 0. Entonces α=w\alpha = w, que es una cadena de terminales. El PDA usa ∣w∣|w| veces las transiciones de comparar: cada una lee un símbolo de ww y saca el mismo símbolo de la cima.

Paso inductivo: supongamos la afirmación para nn, y sea α⇒β⇒∗w\alpha \Rightarrow \beta \Rightarrow^* w una derivación por la izquierda de n+1n + 1 pasos. El primer paso reemplaza la variable de más a la izquierda: α=xAα′\alpha = xA\alpha' con x∈Σ∗x \in \Sigma^*, y β=xηα′\beta = x\eta\alpha', donde A→ηA \to \eta es una regla. Por el segundo hecho, w=xw′w = xw' y ηα′\eta\alpha' deriva w′w' por la izquierda en nn pasos. Entonces el PDA puede hacer esto:

(qloop,xw′y,xAα′γ)⊢∗(qloop,w′y,Aα′γ)comparar los sıˊmbolos de x⊢∗(qloop,w′y,ηα′γ)reemplazar con la regla A→η⊢∗(qloop,y,γ)hipoˊtesis de induccioˊn, con ηα′ y w′\begin{aligned} (q_{\text{loop}}, xw'y, xA\alpha'\gamma) &\vdash^* (q_{\text{loop}}, w'y, A\alpha'\gamma) && \text{comparar los símbolos de } x \\ &\vdash^* (q_{\text{loop}}, w'y, \eta\alpha'\gamma) && \text{reemplazar con la regla } A \to \eta \\ &\vdash^* (q_{\text{loop}}, y, \gamma) && \text{hipótesis de inducción, con } \eta\alpha' \text{ y } w' \end{aligned}

El segundo renglón son las transiciones del punto 2 de la construcción: una sola si η\eta tiene cero o un símbolo, y ∣η∣|\eta| pasando por los estados intermedios de la regla si tiene más. ∎

Afirmación 2 (lo que el PDA consume, la gramática lo deriva). Si

(qloop,xy,S$)⊢∗(qloop,y,β$),(q_{\text{loop}}, xy, S\texttt{\textdollar}) \vdash^* (q_{\text{loop}}, y, \beta\texttt{\textdollar}),

entonces S⇒∗xβS \Rightarrow^* x\beta.

Demostración. Primero, qué puede hacer PP desde qloopq_{\text{loop}}. Tiene cuatro tipos de transiciones. Las de comparar y las de reemplazar con k≤1k \leq 1 vuelven a qloopq_{\text{loop}} en un paso. Las de reemplazar con k≥2k \geq 2 pasan a r1r_1; cada estado intermedio tiene una sola transición, que no lee ni saca nada y por eso siempre se puede usar, así que la máquina recorre r1,…,rk−1r_1, \ldots, r_{k-1} y vuelve a qloopq_{\text{loop}} con X1⋯XkX_1 \cdots X_k en lugar de AA. Y la de terminar saca $ y sale a qacceptq_{\text{accept}}, de donde no hay vuelta. Llamemos tramo a cada trozo de ejecución que va de qloopq_{\text{loop}} a la siguiente vez en qloopq_{\text{loop}}. Un tramo es una comparación o un reemplazo completo. Como $ se pone una sola vez y solo se saca al salir, en qloopq_{\text{loop}} la pila siempre tiene la forma β$\beta\texttt{\textdollar} con β∈(V∪Σ)∗\beta \in (V \cup \Sigma)^*.

Ahora, inducción sobre la cantidad de tramos de la ejecución.

Caso base: cero tramos. No se leyó nada y la pila no cambió: x=εx = \varepsilon y β=S\beta = S. Y S⇒∗SS \Rightarrow^* S en cero pasos.

Paso inductivo: supongamos la afirmación para ejecuciones de nn tramos, y tomemos una de n+1n + 1. Antes del último tramo se había leído x1x_1 y la pila era β1$\beta_1\texttt{\textdollar}, y por hipótesis S⇒∗x1β1S \Rightarrow^* x_1\beta_1. El último tramo es de uno de dos tipos.

  • Comparación con un terminal aa: entonces β1=aβ\beta_1 = a\beta y x=x1ax = x_1a. Luego xβ=x1aβ=x1β1x\beta = x_1a\beta = x_1\beta_1, y S⇒∗xβS \Rightarrow^* x\beta es la hipótesis.
  • Reemplazo con una regla A→ηA \to \eta: entonces β1=Aβ′\beta_1 = A\beta', β=ηβ′\beta = \eta\beta' y x=x1x = x_1. Luego S⇒∗x1Aβ′⇒x1ηβ′=xβS \Rightarrow^* x_1A\beta' \Rightarrow x_1\eta\beta' = x\beta: un paso más de derivación. ∎

Demostración del teorema. Sea w∈Σ∗w \in \Sigma^*.

Si w∈L(G)w \in L(G), entonces PP acepta ww. Por el primer hecho, SS deriva ww por la izquierda. La afirmación 1, con α=S\alpha = S, y=εy = \varepsilon y γ=$\gamma = \texttt{\textdollar}, da el tramo central de esta ejecución:

(qstart,w,ε)⊢(qbegin,w,$)⊢(qloop,w,S$)⊢∗(qloop,ε,$)⊢(qaccept,ε,ε)(q_{\text{start}}, w, \varepsilon) \vdash (q_{\text{begin}}, w, \texttt{\textdollar}) \vdash (q_{\text{loop}}, w, S\texttt{\textdollar}) \vdash^* (q_{\text{loop}}, \varepsilon, \texttt{\textdollar}) \vdash (q_{\text{accept}}, \varepsilon, \varepsilon)

Si PP acepta ww, entonces w∈L(G)w \in L(G). Una ejecución que acepta termina en qacceptq_{\text{accept}}, el único estado de aceptación, con toda la entrada leída. Sus dos primeros pasos son obligados y la dejan en (qloop,w,S$)(q_{\text{loop}}, w, S\texttt{\textdollar}). A qacceptq_{\text{accept}} solo se entra desde qloopq_{\text{loop}} sacando $, y como qacceptq_{\text{accept}} no tiene transiciones, en ese momento ya no faltaba leer nada. Además, si $ está en la cima, encima de él no hay nada. Así que la ejecución pasó por (qloop,ε,$)(q_{\text{loop}}, \varepsilon, \texttt{\textdollar}), y la afirmación 2 con x=wx = w, y=εy = \varepsilon y β=ε\beta = \varepsilon da S⇒∗wS \Rightarrow^* w. ∎

test_convert comprueba el teorema con siete gramáticas: para cada una construye el PDA y compara, cadena por cadena hasta cierta longitud, lo que el PDA acepta con lo que la gramática genera.

Un PDA que no se deja simular

La gramática de expresiones sin ambigüedad de la semana 5 está en machines/expr.cfg:

E→E+T∣TT→T∗F∣FF→(E)∣aE \to E + T \mid T \qquad T \to T * F \mid F \qquad F \to \mathtt{(}E\mathtt{)} \mid \mathtt{a}

Su PDA tiene 10 estados. Con una cadena del lenguaje, la búsqueda encuentra la ejecución. Con una que no lo es, pasa otra cosa:

$ build/cfg_to_pda machines/expr.cfg > build/expr.pda
$ build/run_pda --limite 5000 build/expr.pda 'a+a' 'a+'
w = a+a
  paso  transición  estado    falta leer  pila
     0              q_start   a+a         ε
     1  ε, ε → $    q_begin   a+a         $
     2  ε, ε → E    q_loop    a+a         E$
     3  ε, E → T    r1_1      a+a         T$
     4  ε, ε → +    r1_2      a+a         +T$
     5  ε, ε → E    q_loop    a+a         E+T$
     6  ε, E → T    q_loop    a+a         T+T$
     7  ε, T → F    q_loop    a+a         F+T$
     8  ε, F → a    q_loop    a+a         a+T$
     9  a, a → ε    q_loop    +a          +T$
    10  +, + → ε    q_loop    a           T$
    11  ε, T → F    q_loop    a           F$
    12  ε, F → a    q_loop    a           a$
    13  a, a → ε    q_loop    ε           $
    14  ε, $ → ε    q_accept  ε           ε
  acepta en q_accept (configuraciones exploradas: 107)
w = a+
  límite: más de 5000 configuraciones, sin aceptar

La cadena a+ no es una expresión, y aun así el programa no puede decir “rechaza”. La culpa es de la regla E→E+TE \to E + T, que es recursiva por la izquierda: su lado derecho empieza con la misma variable. Las filas 2 a 5 muestran lo que eso le hace al PDA: sin leer nada, la pila pasó de E$ a E+T$. La cima vuelve a ser EE, y nada impide repetirlo: E+T+T$, E+T+T+T$, y así sin fin. Es un ciclo de transiciones ε\varepsilon que hace crecer la pila, y las configuraciones alcanzables son infinitas.

El teorema no se resiente: habla de si existe una ejecución de aceptación, y para a+ no existe. Lo que falla es nuestro método para comprobarlo, la búsqueda exhaustiva. La construcción produce un PDA correcto, pero no un buen algoritmo. Los parsers reales resuelven esto de otra manera, y es el tema de la sección opcional del final.

De PDA a gramática

La otra mitad del teorema va en sentido contrario.

Teorema. Para todo PDA PP existe una gramática libre de contexto GG con L(G)=L(P)L(G) = L(P).

Esta dirección es más difícil, porque hay que sacar una gramática de una máquina que puede hacer cosas muy desordenadas con su pila. En clase se ve la idea y un ejemplo. La demostración completa está al final de la sección, para leerla con calma.

La idea: las variables A_pq

Miren la altura de la pila durante una ejecución, como un perfil de montaña. En la de 0011\mathtt{0011} sube, sube, sube, baja, baja, baja. En la de los paréntesis (())() sube y baja dos veces. En todos los casos, si la ejecución empieza y termina con la pila vacía, el perfil empieza y termina en el suelo.

La gramática va a tener una variable ApqA_{pq} por cada par de estados pp y qq, con este significado:

Apq genera exactamente las cadenas que llevan a P del estado p con la pila vacıˊa al estado q con la pila vacıˊa.A_{pq} \text{ genera exactamente las cadenas que llevan a } P \text{ del estado } p \text{ con la pila vacía al estado } q \text{ con la pila vacía.}

Por el lema del fondo, “con la pila vacía” se puede leer también como “dejando la pila como estaba, sin tocar lo que había debajo”: una ejecución que va de vacía a vacía se puede repetir encima de cualquier pila.

¿Qué reglas necesita ApqA_{pq}? Tomemos una cadena xx que lleva de pp a qq de pila vacía a pila vacía, y miremos el perfil. Hay solo dos formas posibles.

Dos gráficos de la altura de la pila a lo largo de los pasos de una ejecución que va del estado p al estado q, de pila vacía a pila vacía. Cada paso sube o baja la altura en uno. En el gráfico (a) el perfil no toca el suelo en el medio: el primer paso, resaltado, lee a y pone u, y lleva de p a r; el último, también resaltado, lee b y saca u, y lleva de s a q. Entre r y s hay una franja a la altura del primer símbolo con la nota de que u sigue en el fondo, y la parte del perfil que queda encima es lo que genera A_rs: una cadena y que lleva de r a s sin tocar u. Arriba, la regla A_pq → a A_rs b. En el gráfico (b) el perfil sube, baja hasta el suelo en un estado r, donde la pila está vacía, y vuelve a subir y bajar: el primer tramo es lo que genera A_pr, una cadena y que lleva de p a r, y el segundo lo que genera A_rq, una cadena z que lleva de r a q. Arriba, la regla A_pq → A_pr A_rq. Al pie: en un PDA normalizado cada paso pone o saca un símbolo, así que el perfil solo puede tener estas dos formas; y el caso base, sin moverse, es A_pp → εDos gráficos de la altura de la pila a lo largo de los pasos de una ejecución que va del estado p al estado q, de pila vacía a pila vacía. Cada paso sube o baja la altura en uno. En el gráfico (a) el perfil no toca el suelo en el medio: el primer paso, resaltado, lee a y pone u, y lleva de p a r; el último, también resaltado, lee b y saca u, y lleva de s a q. Entre r y s hay una franja a la altura del primer símbolo con la nota de que u sigue en el fondo, y la parte del perfil que queda encima es lo que genera A_rs: una cadena y que lleva de r a s sin tocar u. Arriba, la regla A_pq → a A_rs b. En el gráfico (b) el perfil sube, baja hasta el suelo en un estado r, donde la pila está vacía, y vuelve a subir y bajar: el primer tramo es lo que genera A_pr, una cadena y que lleva de p a r, y el segundo lo que genera A_rq, una cadena z que lleva de r a q. Arriba, la regla A_pq → A_pr A_rq. Al pie: en un PDA normalizado cada paso pone o saca un símbolo, así que el perfil solo puede tener estas dos formas; y el caso base, sin moverse, es A_pp → ε
Las dos formas del perfil. Si no toca el suelo, el símbolo que pone el primer paso es el que saca el último; si lo toca, la ejecución se parte ahí en dos.
  • (a) La pila no se vacía en el medio. Entonces el símbolo que se puso en el primer paso se queda en el fondo todo el tiempo, y es el que se saca en el último paso. Si el primer paso lee aa y va a un estado rr, y el último lee bb y viene de un estado ss, lo que pasa en el medio lleva de rr a ss sin tocar ese símbolo del fondo: es una cadena de ArsA_{rs}. La regla es Apq→aArsbA_{pq} \to aA_{rs}b.
  • (b) La pila se vacía en algún momento intermedio, en un estado rr. Entonces xx se parte en dos trozos: el primero lleva de pp a rr y el segundo de rr a qq, los dos de pila vacía a pila vacía. La regla es Apq→AprArqA_{pq} \to A_{pr}A_{rq}.

Y un caso base: sin hacer nada, la máquina va de pp a pp. La regla es App→εA_{pp} \to \varepsilon.

Idea clave. La variable ApqA_{pq} resume todo lo que el PDA puede hacer entre pp y qq dejando la pila como la encontró. La regla Apq→aArsbA_{pq} \to aA_{rs}b empareja el paso que pone un símbolo con el paso que lo saca: es el mismo emparejamiento que hace S→0S1S \to \mathtt{0}S\mathtt{1} entre un cero y su uno.

Primero, ordenar el PDA

El argumento del perfil necesita que la máquina sea ordenada en tres sentidos. Diremos que un PDA está normalizado si:

  1. tiene un solo estado de aceptación, qacceptq_{\text{accept}};
  2. vacía la pila antes de aceptar: siempre que está en qacceptq_{\text{accept}}, la pila está vacía;
  3. cada transición pone un símbolo o saca un símbolo, pero no las dos cosas ni ninguna de las dos.

Con 1 y 2, aceptar es “ir de q0q_0 con la pila vacía a qacceptq_{\text{accept}} con la pila vacía”, que es justo lo que describe una variable ApqA_{pq}. Con 3, cada paso sube o baja la altura en exactamente uno, y el perfil es una línea que nunca queda plana ni cambia un símbolo por otro a la misma altura.

Todo PDA se puede normalizar sin cambiar su lenguaje.

  • Para 1 y 2. Se agrega un estado inicial nuevo que pone una marca de fondo nueva, ⊥\bot, que no está en Γ\Gamma, y pasa al estado inicial viejo. Se agregan un estado qdrainq_{\text{drain}} y el nuevo qacceptq_{\text{accept}}. Desde cada estado de aceptación viejo hay una transición ε\varepsilon a qdrainq_{\text{drain}}. En qdrainq_{\text{drain}}, por cada símbolo cc de Γ\Gamma, una transición ε,c→ε\varepsilon, c \to \varepsilon a sí mismo: vacía la pila. Y de qdrainq_{\text{drain}} a qacceptq_{\text{accept}}, la transición ε,⊥→ε\varepsilon, \bot \to \varepsilon. El único estado de aceptación es el nuevo.
  • Para 3. Una transición que saca bb y pone cc se cambia por dos, con un estado intermedio nuevo: la primera lee lo que leía la original y saca bb, la segunda pone cc. Una transición que no saca ni pone se cambia por dos: la primera lee y pone un símbolo de relleno, la segunda lo saca.

Por qué no cambia el lenguaje. La máquina vieja nunca ve la marca ⊥\bot, porque no está en su alfabeto: no puede sacarla, y todo lo que hace lo hace encima de ella, igual que antes (lema del fondo). Si la vieja acepta ww, la nueva hace lo mismo, salta a qdrainq_{\text{drain}}, vacía y acepta. Al revés, la nueva solo llega a qacceptq_{\text{accept}} pasando por qdrainq_{\text{drain}}, al que solo se entra desde un estado de aceptación viejo; y como qdrainq_{\text{drain}} y qacceptq_{\text{accept}} no leen, en ese momento la entrada ya estaba leída, así que la vieja también aceptaba. Al llegar a qacceptq_{\text{accept}} se acaba de sacar ⊥\bot, que estaba en el fondo: la pila está vacía. Las transiciones partidas en dos hacen lo mismo que la original, porque al estado intermedio solo se entra por la primera mitad y solo se sale por la segunda.

El programa normalize_pda hace exactamente esto, con @ como marca y % como relleno. El autómata de machines/zeros_ones.pda, de 4 estados, queda con 9. Para el ejemplo de clase usaremos uno normalizado a mano, que es más pequeño.

Un ejemplo pequeño

El archivo machines/zeros_ones_norm.pda es el autómata de 0n1n\mathtt{0}^n\mathtt{1}^n con dos cambios: q0q_0 ya no es de aceptación, y hay una transición más, de q1q_1 a q3q_3, para aceptar la cadena vacía.

Estado Lee, saca →\to pone Destino Tipo
q0q_0 ε,ε→$\varepsilon, \varepsilon \to \texttt{\textdollar} q1q_1 pone
q1q_1 0,ε→0\mathtt{0}, \varepsilon \to \mathtt{0} q1q_1 pone
q1q_1 1,0→ε\mathtt{1}, \mathtt{0} \to \varepsilon q2q_2 saca
q2q_2 1,0→ε\mathtt{1}, \mathtt{0} \to \varepsilon q2q_2 saca
q1q_1 ε,$→ε\varepsilon, \texttt{\textdollar} \to \varepsilon q3q_3 saca
q2q_2 ε,$→ε\varepsilon, \texttt{\textdollar} \to \varepsilon q3q_3 saca

Está normalizado: un solo estado de aceptación, q3q_3; a q3q_3 solo se entra sacando $, que es el fondo; y cada transición pone o saca. La variable inicial de la gramática será Aq0q3A_{q_0q_3}, que escribimos A03A_{03}.

Las reglas del tipo Apq→aArsbA_{pq} \to aA_{rs}b salen de emparejar cada transición que pone un símbolo con cada transición que saca ese mismo símbolo.

  • El símbolo $ lo pone la transición de q0q_0 a q1q_1, sin leer. Lo sacan dos: la de q1q_1 a q3q_3 y la de q2q_2 a q3q_3, sin leer. Con la primera, p=q0p = q_0, r=q1r = q_1, s=q1s = q_1, q=q3q = q_3 y a=b=εa = b = \varepsilon: la regla es A03→A11A_{03} \to A_{11}. Con la segunda, s=q2s = q_2: la regla es A03→A12A_{03} \to A_{12}.
  • El símbolo 0\mathtt{0} lo pone la transición de q1q_1 a q1q_1, leyendo 0\mathtt{0}. Lo sacan dos: la de q1q_1 a q2q_2 y la de q2q_2 a q2q_2, las dos leyendo 1\mathtt{1}. Dan A12→0A111A_{12} \to \mathtt{0}A_{11}\mathtt{1} y A12→0A121A_{12} \to \mathtt{0}A_{12}\mathtt{1}.

Son cuatro reglas. A eso se suman las 43=644^3 = 64 del tipo Apq→AprArqA_{pq} \to A_{pr}A_{rq}, una por cada terna de estados, y las 4 del tipo App→εA_{pp} \to \varepsilon: 72 en total, con 42=164^2 = 16 variables. El programa pda_to_cfg construye la gramática y quita las variables que no generan nada o que no se alcanzan desde la inicial:

$ build/pda_to_cfg machines/zeros_ones_norm.pda
# Gramática del PDA machines/zeros_ones_norm.pda.
# La construcción da 16 variables y 72 reglas.
# Sirven 6 variables y 16 reglas.
variables: A(q0,q0) A(q0,q3) A(q1,q1) A(q1,q2) A(q2,q2) A(q3,q3)
terminals: 0 1
start: A(q0,q3)
rules:
A(q0,q0) -> A(q0,q0) A(q0,q0) | eps
A(q0,q3) -> A(q1,q1) | A(q1,q2) | A(q0,q0) A(q0,q3) | A(q0,q3) A(q3,q3)
A(q1,q1) -> A(q1,q1) A(q1,q1) | eps
A(q1,q2) -> 0 A(q1,q1) 1 | 0 A(q1,q2) 1 | A(q1,q1) A(q1,q2) | A(q1,q2) A(q2,q2)
A(q2,q2) -> A(q2,q2) A(q2,q2) | eps
A(q3,q3) -> A(q3,q3) A(q3,q3) | eps

Las cuatro reglas que calculamos a mano están ahí. La gramática es fea, pero se puede leer. Las variables A00A_{00}, A11A_{11}, A22A_{22} y A33A_{33} solo generan ε\varepsilon: ir de un estado a sí mismo sin tocar la pila, en este autómata, solo se logra sin moverse. Reemplazándolas por ε\varepsilon y borrando las reglas que quedan como X→XX \to X, queda

A03→ε∣A12A12→01∣0A121A_{03} \to \varepsilon \mid A_{12} \qquad A_{12} \to \mathtt{01} \mid \mathtt{0}A_{12}\mathtt{1}

que es la gramática de 0n1n\mathtt{0}^n\mathtt{1}^n de siempre, con otro nombre. Las reglas dicen lo que el autómata hace: A12A_{12} son las maneras de ir de q1q_1 a q2q_2 dejando la pila igual, y cada una empieza poniendo un 0\mathtt{0} y termina sacándolo con un 1\mathtt{1}. Para comprobar que la gramática completa genera lo que debe, se la damos a cfg_strings:

$ build/pda_to_cfg machines/zeros_ones_norm.pda > build/z.cfg
$ build/cfg_strings build/z.cfg 8
5 cadenas de longitud a lo sumo 8:
  ε 01 0011 000111 00001111

La construcción es correcta pero derrochadora. Para el autómata de los palíndromos, normalizado con normalize_pda, da 81 variables y 749 reglas, de las que sirven 14 y 35. Nadie escribe gramáticas así: el valor de la construcción es que existe, y con ella el teorema.

La demostración, completa

Qué se construye. Sea P=(Q,Σ,Γ,δ,q0,{qaccept})P = (Q, \Sigma, \Gamma, \delta, q_0, \{q_{\text{accept}}\}) un PDA normalizado. La gramática GG tiene las variables { Apq:p,q∈Q }\{\, A_{pq} : p, q \in Q \,\}, los terminales Σ\Sigma, la variable inicial Aq0qacceptA_{q_0q_{\text{accept}}} y estas reglas:

  1. Para cada p,q,r,s∈Qp, q, r, s \in Q, cada u∈Γu \in \Gamma y cada a,b∈Σεa, b \in \Sigma_\varepsilon: si (r,u)∈δ(p,a,ε)(r, u) \in \delta(p, a, \varepsilon) y (q,ε)∈δ(s,b,u)(q, \varepsilon) \in \delta(s, b, u), la regla Apq→aArsbA_{pq} \to aA_{rs}b.
  2. Para cada p,q,r∈Qp, q, r \in Q: la regla Apq→AprArqA_{pq} \to A_{pr}A_{rq}.
  3. Para cada p∈Qp \in Q: la regla App→εA_{pp} \to \varepsilon.

Por qué genera L(P)L(P). Diremos que una cadena x∈Σ∗x \in \Sigma^* lleva de pp a qq con la pila vacía si (p,x,ε)⊢∗(q,ε,ε)(p, x, \varepsilon) \vdash^* (q, \varepsilon, \varepsilon). Hay que demostrar que ApqA_{pq} genera xx si y solo si xx lleva de pp a qq con la pila vacía. Son dos afirmaciones.

Afirmación 1. Si Apq⇒∗xA_{pq} \Rightarrow^* x, entonces xx lleva de pp a qq con la pila vacía.

Demostración. Por inducción sobre la cantidad de pasos de la derivación.

Caso base: un paso. La regla usada no tiene variables a la derecha, así que es App→εA_{pp} \to \varepsilon. Entonces q=pq = p y x=εx = \varepsilon, y (p,ε,ε)⊢∗(p,ε,ε)(p, \varepsilon, \varepsilon) \vdash^* (p, \varepsilon, \varepsilon) en cero pasos.

Paso inductivo: supongamos la afirmación para las derivaciones de a lo sumo kk pasos, con k≥1k \geq 1, y sea Apq⇒∗xA_{pq} \Rightarrow^* x una de k+1k + 1. Su primer paso usa una regla del tipo 1 o del tipo 2.

  • Tipo 1: Apq⇒aArsb⇒∗xA_{pq} \Rightarrow aA_{rs}b \Rightarrow^* x. Entonces x=aybx = ayb, donde Ars⇒∗yA_{rs} \Rightarrow^* y en kk pasos. Por hipótesis, (r,y,ε)⊢∗(s,ε,ε)(r, y, \varepsilon) \vdash^* (s, \varepsilon, \varepsilon). Por el lema del fondo, con z=bz = b y γ=u\gamma = u: (r,yb,u)⊢∗(s,b,u)(r, yb, u) \vdash^* (s, b, u). Y la regla existe porque PP tiene las transiciones (r,u)∈δ(p,a,ε)(r, u) \in \delta(p, a, \varepsilon) y (q,ε)∈δ(s,b,u)(q, \varepsilon) \in \delta(s, b, u). Juntando:
(p,ayb,ε)⊢(r,yb,u)⊢∗(s,b,u)⊢(q,ε,ε).(p, ayb, \varepsilon) \vdash (r, yb, u) \vdash^* (s, b, u) \vdash (q, \varepsilon, \varepsilon).
  • Tipo 2: Apq⇒AprArq⇒∗xA_{pq} \Rightarrow A_{pr}A_{rq} \Rightarrow^* x. Entonces x=yzx = yz con Apr⇒∗yA_{pr} \Rightarrow^* y y Arq⇒∗zA_{rq} \Rightarrow^* z, cada una en a lo sumo kk pasos, porque lo que deriva cada variable no depende de la otra. Por hipótesis, yy lleva de pp a rr y zz lleva de rr a qq, con la pila vacía. Por el lema del fondo aplicado a la primera, con zz detrás: (p,yz,ε)⊢∗(r,z,ε)⊢∗(q,ε,ε)(p, yz, \varepsilon) \vdash^* (r, z, \varepsilon) \vdash^* (q, \varepsilon, \varepsilon). ∎

Afirmación 2. Si xx lleva de pp a qq con la pila vacía, entonces Apq⇒∗xA_{pq} \Rightarrow^* x.

Demostración. Por inducción sobre la cantidad de pasos de la ejecución (p,x,ε)⊢∗(q,ε,ε)(p, x, \varepsilon) \vdash^* (q, \varepsilon, \varepsilon).

Caso base: cero pasos. Entonces q=pq = p y x=εx = \varepsilon, y GG tiene la regla App→εA_{pp} \to \varepsilon.

Paso inductivo: supongamos la afirmación para las ejecuciones de a lo sumo kk pasos, y sea C0⊢C1⊢⋯⊢Ck+1C_0 \vdash C_1 \vdash \cdots \vdash C_{k+1} una de k+1k + 1, con C0=(p,x,ε)C_0 = (p, x, \varepsilon) y Ck+1=(q,ε,ε)C_{k+1} = (q, \varepsilon, \varepsilon). Hay dos casos, según la pila de las configuraciones intermedias C1,…,CkC_1, \ldots, C_k.

Caso (b): alguna configuración intermedia CiC_i tiene la pila vacía. Sea rr su estado, yy lo que se leyó hasta ahí y zz lo que falta, de modo que x=yzx = yz y Ci=(r,z,ε)C_i = (r, z, \varepsilon). La segunda parte, Ci⊢∗Ck+1C_i \vdash^* C_{k+1}, dice que zz lleva de rr a qq con la pila vacía, en a lo sumo kk pasos. La primera parte es (p,yz,ε)⊢∗(r,z,ε)(p, yz, \varepsilon) \vdash^* (r, z, \varepsilon); como sus pasos no leen nada de zz, quitando zz del final de cada configuración queda (p,y,ε)⊢∗(r,ε,ε)(p, y, \varepsilon) \vdash^* (r, \varepsilon, \varepsilon), también de a lo sumo kk pasos. Por hipótesis, Apr⇒∗yA_{pr} \Rightarrow^* y y Arq⇒∗zA_{rq} \Rightarrow^* z. Con la regla del tipo 2: Apq⇒AprArq⇒∗yz=xA_{pq} \Rightarrow A_{pr}A_{rq} \Rightarrow^* yz = x.

Caso (a): todas las configuraciones intermedias tienen la pila no vacía. Aquí se usa la condición 3: cada paso pone un símbolo o saca uno.

  • El primer paso sale de la pila vacía, así que no puede sacar: pone un símbolo uu. Sea aa lo que lee y rr el estado al que va: (r,u)∈δ(p,a,ε)(r, u) \in \delta(p, a, \varepsilon), y C1C_1 tiene la pila uu.
  • Con una sola transición no se va de la pila vacía a la pila vacía, así que k+1≥2k + 1 \geq 2 y C1C_1 es una configuración intermedia distinta de la última.
  • Durante C1,…,CkC_1, \ldots, C_k ese símbolo uu no se mueve del fondo. Un paso solo cambia la cima. Para sacar el símbolo del fondo, tendría que ser el único de la pila, y al sacarlo la pila quedaría vacía en una configuración intermedia, cosa que en este caso no pasa.
  • El último paso va de CkC_k, con la pila no vacía, a Ck+1C_{k+1}, con la pila vacía: saca, y lo que saca es el único símbolo que quedaba, que es uu. Sea bb lo que lee y ss el estado del que sale: (q,ε)∈δ(s,b,u)(q, \varepsilon) \in \delta(s, b, u), y Ck=(s,b,u)C_k = (s, b, u).

Entonces GG tiene la regla Apq→aArsbA_{pq} \to aA_{rs}b. Además x=aybx = ayb, donde yy es lo que se lee entre C1C_1 y CkC_k, y la parte central de la ejecución es

(r,yb,u)⊢∗(s,b,u),(r, yb, u) \vdash^* (s, b, u),

con k−1k - 1 pasos y con uu quieto en el fondo. Quitemos de cada una de sus configuraciones la bb del final de la entrada y la uu del fondo de la pila. Lo que queda sigue siendo una ejecución: ningún paso lee la bb, y ningún paso saca la uu, así que cada paso usa su transición igual que antes. Es decir, (r,y,ε)⊢∗(s,ε,ε)(r, y, \varepsilon) \vdash^* (s, \varepsilon, \varepsilon) en k−1k - 1 pasos. Por hipótesis, Ars⇒∗yA_{rs} \Rightarrow^* y, y entonces Apq⇒aArsb⇒∗ayb=xA_{pq} \Rightarrow aA_{rs}b \Rightarrow^* ayb = x. ∎

Demostración del teorema. Dado un PDA cualquiera, se lo normaliza. Por las condiciones 1 y 2, el PDA normalizado acepta xx si y solo si (q0,x,ε)⊢∗(qaccept,ε,ε)(q_0, x, \varepsilon) \vdash^* (q_{\text{accept}}, \varepsilon, \varepsilon): acepta solo en qacceptq_{\text{accept}}, y ahí la pila está vacía. Por las dos afirmaciones, eso pasa si y solo si Aq0qaccept⇒∗xA_{q_0q_{\text{accept}}} \Rightarrow^* x, es decir, si y solo si x∈L(G)x \in L(G). ∎

Dónde se usó cada condición: la 1 y la 2, en la última línea, para que aceptar sea “de pila vacía a pila vacía”. La 3, en el caso (a), para saber que el primer paso pone, el último saca, y lo que se saca es lo que se puso. Sin la 3 habría transiciones que reemplazan la cima sin cambiar la altura, y el símbolo del fondo podría cambiar por el camino.

test_convert comprueba el teorema con los ocho autómatas de machines/: normaliza cada uno, verifica que el normalizado acepta lo mismo y con la pila vacía, construye la gramática, y compara lo que genera con lo que el autómata acepta.

Lo que dice la equivalencia

Juntando las dos construcciones:

Teorema. Un lenguaje es libre de contexto si y solo si algún autómata de pila lo reconoce.

Es el análogo del teorema de Kleene de la semana 3. Allá, las expresiones regulares y los autómatas finitos resultaron dos maneras de describir la misma clase. Aquí, las gramáticas y los autómatas de pila. Y como allá, tener las dos caras sirve para elegir: algunas propiedades se demuestran más fácil con gramáticas y otras con autómatas. En la sesión B usaremos las dos.

Una consecuencia inmediata:

Corolario. Todo lenguaje regular es libre de contexto.

Demostración. Un autómata finito es un PDA que no usa la pila. Dado un DFA (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F), el PDA con los mismos estados, Γ=∅\Gamma = \emptyset, y δ′(q,a,ε)={(δ(q,a),ε)}\delta'(q, a, \varepsilon) = \{(\delta(q, a), \varepsilon)\} para cada estado qq y cada símbolo aa, pasa por los mismos estados que el DFA con cada cadena, y acepta las mismas. ∎

El archivo machines/even_ones.pda es el DFA de la paridad de la semana 1 escrito así, con el campo stack: vacío:

$ build/run_pda machines/even_ones.pda 0110
w = 0110
  paso  transición  estado  falta leer  pila
     0              par     0110        ε
     1  0, ε → ε    par     110         ε
     2  1, ε → ε    impar   10          ε
     3  1, ε → ε    par     0           ε
     4  0, ε → ε    par     ε           ε
  acepta en par (configuraciones exploradas: 5)

La semana 5 dio otra demostración del mismo hecho, con gramáticas: de un DFA sale una gramática con una variable por estado. La inclusión es estricta, porque { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} es libre de contexto y no es regular.

El PDA determinista reconoce menos

En la semana 2, el no determinismo resultó una comodidad: todo NFA tiene un DFA equivalente, aunque sea exponencialmente más grande. Con los autómatas de pila la historia es distinta.

Un PDA es determinista si en ninguna configuración tiene más de una transición que pueda usar. En términos de δ\delta: cada valor δ(q,a,b)\delta(q, a, b) tiene a lo sumo un elemento, y para cada estado qq, cada símbolo a∈Σa \in \Sigma y cada b∈Γb \in \Gamma, a lo sumo uno de los cuatro valores

δ(q,a,b),δ(q,a,ε),δ(q,ε,b),δ(q,ε,ε)\delta(q, a, b), \quad \delta(q, a, \varepsilon), \quad \delta(q, \varepsilon, b), \quad \delta(q, \varepsilon, \varepsilon)

no es vacío. Son las cuatro maneras de moverse cuando el siguiente símbolo es aa y la cima es bb.

El autómata de 0n1n\mathtt{0}^n\mathtt{1}^n es determinista: en q1q_1, por ejemplo, con un 0\mathtt{0} por leer solo puede poner, y con un 1\mathtt{1} solo puede sacar. El de los palíndromos no lo es: en q1q_1 no son vacíos δ(q1,0,ε)\delta(q_1, \mathtt{0}, \varepsilon), seguir guardando, y δ(q1,ε,ε)\delta(q_1, \varepsilon, \varepsilon), saltar al medio.

Teorema (sin demostración). Ningún PDA determinista reconoce { wwR:w∈{0,1}∗ }\{\, ww^R : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\}.

La demostración es larga y no la haremos. La intuición es la que ya vimos: para comparar las dos mitades hay que empezar a sacar justo en el medio, y nada en la entrada dice dónde está. Una máquina determinista tendría que decidirlo mirando solo lo leído hasta el momento. Si después de 0110\mathtt{0110} decide que ahí terminó un palíndromo y vacía la pila para comprobarlo, perdió lo que necesitaba para seguir con 0110 0110\mathtt{0110}\,\mathtt{0110}, que también es un palíndromo. Si no lo comprueba, no puede aceptar 0110\mathtt{0110}. Esto es solo una intuición: que ninguna máquina determinista encuentra una salida es lo que el teorema afirma.

Con una señal en el medio, el problema desaparece: { w#wR }\{\, w\mathtt{\#}w^R \,\} sí tiene un PDA determinista, que guarda hasta ver el #\mathtt{\#} y después saca.

Idea clave. En los autómatas finitos, el no determinismo no agrega poder: NFA y DFA reconocen los mismos lenguajes. En los autómatas de pila, sí: hay lenguajes libres de contexto que ningún PDA determinista reconoce. Por eso la definición de PDA es no determinista desde el principio.

Los lenguajes que sí tienen un PDA determinista se llaman libres de contexto deterministas. Son una clase intermedia, estrictamente entre los regulares y los libres de contexto, y son los que importan en la práctica: la sintaxis de los lenguajes de programación se diseña para caer ahí, porque un lenguaje que tiene un PDA determinista se puede reconocer en tiempo lineal, sin búsqueda. La sección opcional del final muestra uno.

Un lenguaje que pide comparar tres cantidades

Hasta aquí todo fueron construcciones. Ahora toca el límite. El candidato es el lenguaje más simple que compara tres cosas en lugar de dos:

D={ anbncn:n≥0 }={ε,abc,aabbcc,aaabbbccc,…}D = \{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\} = \{\varepsilon, \mathtt{abc}, \mathtt{aabbcc}, \mathtt{aaabbbccc}, \ldots\}

Antes de demostrar que no es libre de contexto, vale la pena intentar un PDA y ver dónde se rompe. El plan natural: guardar las a\mathtt{a}, sacarlas con las b\mathtt{b}, y después… después la pila está vacía, y las c\mathtt{c} no tienen con qué compararse. El archivo machines/anbn_cm.pda es ese intento: llega hasta las c\mathtt{c} y las deja pasar.

$ build/run_pda machines/anbn_cm.pda aabbcc aabbc
w = aabbcc
  paso  transición  estado  falta leer  pila
     0              q0      aabbcc      ε
     1  ε, ε → $    q1      aabbcc      $
     2  a, ε → a    q1      abbcc       a$
     3  a, ε → a    q1      bbcc        aa$
     4  ε, ε → ε    q2      bbcc        aa$
     5  b, a → ε    q2      bcc         a$
     6  b, a → ε    q2      cc          $
     7  ε, $ → ε    q3      cc          ε
     8  c, ε → ε    q3      c           ε
     9  c, ε → ε    q3      ε           ε
  acepta en q3 (configuraciones exploradas: 13)
w = aabbc
  paso  transición  estado  falta leer  pila
     0              q0      aabbc       ε
     1  ε, ε → $    q1      aabbc       $
     2  a, ε → a    q1      abbc        a$
     3  a, ε → a    q1      bbc         aa$
     4  ε, ε → ε    q2      bbc         aa$
     5  b, a → ε    q2      bc          a$
     6  b, a → ε    q2      c           $
     7  ε, $ → ε    q3      c           ε
     8  c, ε → ε    q3      ε           ε
  acepta en q3 (configuraciones exploradas: 12)

Acepta aabbcc\mathtt{aabbcc}, que está bien, y también aabbc\mathtt{aabbc}, que no está en DD. En la fila 7 de las dos ejecuciones la pila está vacía y el estado es el mismo: la máquina ya no sabe si hubo dos a\mathtt{a} o doscientas. Lo que este autómata reconoce es { anbncm }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^m \,\}, un lenguaje más grande.

Se pueden probar variantes. Guardar dos símbolos por cada a\mathtt{a}, para que alcancen para las b\mathtt{b} y las c\mathtt{c}: pero entonces lo que se comprueba es que j+k=2ij + k = 2i, y aabccc\mathtt{aabccc} pasa. Guardar las a\mathtt{a} y, al sacarlas con las b\mathtt{b}, anotar en otro lado cuántas eran: no hay otro lado, el estado es finito. Todas las variantes chocan con lo mismo: para comparar hay que sacar, y lo que se saca se pierde.

Que varios intentos fallen no demuestra nada. Podría existir un PDA ingenioso que no se nos ocurrió, o una gramática. Para descartarlos a todos de una vez hace falta una propiedad que todos los lenguajes libres de contexto tengan y DD no. Es el mismo plan que en la semana 4.

El lema de bombeo para lenguajes libres de contexto

La idea: un árbol muy alto repite una variable

En la semana 4, el lema de bombeo de los regulares salía de un conteo: una cadena más larga que la cantidad de estados obliga al DFA a repetir un estado, y el tramo entre las dos visitas se puede repetir. Aquí el conteo es sobre el árbol de derivación, y lo que se repite es una variable.

Tomemos una gramática y una cadena ss muy larga de su lenguaje. Cada nodo del árbol tiene pocos hijos, a lo sumo tantos como símbolos tiene el lado derecho más largo de una regla. Un árbol con pocos hijos por nodo y muchísimas hojas tiene que ser alto. Y en un camino de la raíz a una hoja más largo que la cantidad de variables, alguna variable RR aparece dos veces.

Figura en tres partes. A la izquierda, el árbol de derivación de s = uvxyz, dibujado como triángulos anidados: el triángulo grande tiene a S en el vértice y toda la cadena en la base; un camino punteado baja desde S y pasa por dos nodos R. El triángulo de la R de arriba abarca en la base los trozos v, x, y; dentro de él, el triángulo de la R de abajo abarca solo x. A los lados quedan u y z. Debajo, las tres derivaciones que se leen del árbol: S ⇒* uRz, R ⇒* vRy y R ⇒* x, con la nota de que la del medio se puede usar cualquier cantidad de veces, o ninguna. A la derecha arriba, i = 0: el subárbol de la R de abajo puesto en el lugar del de arriba; queda una sola R y la base es u, x, z. A la derecha abajo, i = 2: una copia del subárbol de la R de arriba puesta en lugar del de abajo; hay tres R en el camino y la base es u, v, v, x, y, y, zFigura en tres partes. A la izquierda, el árbol de derivación de s = uvxyz, dibujado como triángulos anidados: el triángulo grande tiene a S en el vértice y toda la cadena en la base; un camino punteado baja desde S y pasa por dos nodos R. El triángulo de la R de arriba abarca en la base los trozos v, x, y; dentro de él, el triángulo de la R de abajo abarca solo x. A los lados quedan u y z. Debajo, las tres derivaciones que se leen del árbol: S ⇒* uRz, R ⇒* vRy y R ⇒* x, con la nota de que la del medio se puede usar cualquier cantidad de veces, o ninguna. A la derecha arriba, i = 0: el subárbol de la R de abajo puesto en el lugar del de arriba; queda una sola R y la base es u, x, z. A la derecha abajo, i = 2: una copia del subárbol de la R de arriba puesta en lugar del de abajo; hay tres R en el camino y la base es u, v, v, x, y, y, z
Una variable repetida en un camino parte la cadena en cinco. Cambiar un subárbol de R por el otro da otro árbol válido: v e y se quitan o se repiten juntas.

La RR de arriba genera un trozo de ss, que llamamos vxyvxy, y dentro de él la RR de abajo genera xx. En términos de derivaciones, el árbol dice tres cosas:

S⇒∗uRz,R⇒∗vRy,R⇒∗x.S \Rightarrow^* uRz, \qquad R \Rightarrow^* vRy, \qquad R \Rightarrow^* x.

La del medio es la importante: de RR se llega otra vez a RR, con vv a la izquierda y yy a la derecha. Nada obliga a usarla una sola vez. Usándola ii veces:

S⇒∗uRz⇒∗uvRyz⇒∗uvvRyyz⇒∗⋯⇒∗uviRyiz⇒∗uvixyiz.S \Rightarrow^* uRz \Rightarrow^* uvRyz \Rightarrow^* uvvRyyz \Rightarrow^* \cdots \Rightarrow^* uv^iRy^iz \Rightarrow^* uv^ixy^iz.

En el árbol, es cortar el subárbol de la RR de abajo y pegar en su lugar una copia del subárbol de la RR de arriba. Y con i=0i = 0: S⇒∗uRz⇒∗uxzS \Rightarrow^* uRz \Rightarrow^* uxz, que es pegar el subárbol de abajo en el lugar del de arriba.

La diferencia con el lema de los regulares es que aquí se repiten dos trozos, vv e yy, y a la vez: la misma cantidad de veces cada uno. Es lo que hace una regla como S→0S1S \to \mathtt{0}S\mathtt{1}, que crece por los dos lados.

El enunciado

Teorema (lema de bombeo para lenguajes libres de contexto). Si AA es un lenguaje libre de contexto, existe un número p≥1p \geq 1, la longitud de bombeo, tal que toda cadena s∈As \in A con ∣s∣≥p|s| \geq p se puede dividir en cinco partes, s=uvxyzs = uvxyz, que cumplen:

  1. uvixyiz∈Auv^ixy^iz \in A para todo i≥0i \geq 0;
  2. ∣vy∣>0|vy| > 0;
  3. ∣vxy∣≤p|vxy| \leq p.

La condición 2 dice que vv e yy no son las dos vacías; una de las dos sí puede serlo. La condición 3 dice que los dos trozos que se repiten están cerca uno del otro: caben, con lo que hay entre ellos, en una ventana de pp símbolos. No dice dónde está esa ventana dentro de ss: a diferencia del lema de los regulares, aquí no hay ninguna garantía de que esté al principio.

La demostración

Qué afirma y con qué técnica. Dada una gramática de AA, se da un valor explícito de pp y se demuestra que sirve. La técnica es el conteo sobre el árbol que acabamos de ver, más un cuidado: elegir el árbol más pequeño.

Sea G=(V,Σ,R,S)G = (V, \Sigma, R, S) una gramática libre de contexto cualquiera con L(G)=AL(G) = A. Sea bb el máximo entre 2 y la cantidad de símbolos del lado derecho más largo de una regla de GG. Definimos

p=b∣V∣+1.p = b^{|V| + 1}.

Paso 1: un árbol bajo tiene pocas hojas. La altura de un árbol es la cantidad de aristas de su camino más largo de la raíz a una hoja. En un árbol de derivación de GG, cada nodo tiene a lo sumo bb hijos. Afirmamos que un árbol de derivación de altura hh genera una cadena de longitud a lo sumo bhb^h. Por inducción sobre hh: con h=1h = 1 la raíz tiene a lo sumo bb hijos y todos son hojas. Un árbol de altura h+1h + 1 tiene una raíz con a lo sumo bb hijos, cada uno una hoja, que aporta a lo sumo un símbolo, o la raíz de un subárbol de altura a lo sumo hh, que por hipótesis genera a lo sumo bhb^h símbolos: en total, a lo sumo b⋅bh=bh+1b \cdot b^h = b^{h+1}.

En consecuencia, si ∣s∣≥p=b∣V∣+1|s| \geq p = b^{|V|+1}, todo árbol de derivación de ss tiene altura al menos ∣V∣+1|V| + 1. Un árbol de altura ∣V∣|V| o menos generaría a lo sumo b∣V∣b^{|V|} símbolos, y b∣V∣<b∣V∣+1b^{|V|} < b^{|V|+1} porque b≥2b \geq 2.

Paso 2: elegir el árbol y encontrar la repetición. Sea s∈As \in A con ∣s∣≥p|s| \geq p. Entre todos los árboles de derivación de ss, sea τ\tau uno con la menor cantidad de nodos. Por el paso 1, τ\tau tiene un camino de la raíz a una hoja con al menos ∣V∣+1|V| + 1 aristas; tomemos el más largo. Ese camino tiene al menos ∣V∣+2|V| + 2 nodos. El último es una hoja, un terminal o ε\varepsilon, y todos los demás son variables: al menos ∣V∣+1|V| + 1 variables.

Miremos las ∣V∣+1|V| + 1 variables más bajas del camino, las más cercanas a la hoja. Son ∣V∣+1|V| + 1 nodos y solo hay ∣V∣|V| variables distintas, así que dos de esos nodos tienen la misma variable, que llamamos RR. Como en el dibujo: la RR de arriba genera vxyvxy, la RR de abajo genera xx, y s=uvxyzs = uvxyz.

Paso 3: las tres condiciones.

Condición 1. Es el argumento de la sección anterior. Del árbol se leen S⇒∗uRzS \Rightarrow^* uRz, R⇒∗vRyR \Rightarrow^* vRy y R⇒∗xR \Rightarrow^* x, y combinándolas se deriva uvixyizuv^ixy^iz para todo i≥0i \geq 0.

Condición 2. Por contradicción. Si v=y=εv = y = \varepsilon, entonces uxz=uvxyz=suxz = uvxyz = s. Reemplacemos en τ\tau el subárbol de la RR de arriba por el de la RR de abajo. El resultado es un árbol de derivación válido, porque en ese lugar sigue habiendo una RR con un subárbol de RR, y genera uxz=suxz = s. Pero tiene menos nodos que τ\tau, porque el subárbol de arriba contiene al de abajo y además, por lo menos, a la RR de arriba. Contradice que τ\tau tenía la menor cantidad de nodos.

Condición 3. La RR de arriba es una de las ∣V∣+1|V| + 1 variables más bajas del camino, así que desde ella hasta la hoja del camino hay a lo sumo ∣V∣+1|V| + 1 aristas. Ese tramo es el camino más largo dentro del subárbol de la RR de arriba: si el subárbol tuviera uno más largo, pegándolo a continuación del tramo que va de la raíz a la RR de arriba saldría un camino en τ\tau más largo que el que elegimos, que era el más largo. Entonces el subárbol de la RR de arriba tiene altura a lo sumo ∣V∣+1|V| + 1 y, por el paso 1, genera a lo sumo b∣V∣+1=pb^{|V|+1} = p símbolos. Lo que genera es vxyvxy. ∎

Tres observaciones sobre la demostración.

El valor de pp sale de la gramática. Para S→0S1∣εS \to \mathtt{0}S\mathtt{1} \mid \varepsilon, el lado derecho más largo tiene 3 símbolos y hay una variable: b=3b = 3 y p=31+1=9p = 3^{1+1} = 9. Una gramática distinta para el mismo lenguaje da otro pp. Al usar el lema para demostrar que un lenguaje no es libre de contexto no se conoce ninguna gramática, justamente porque no existe, y por eso los argumentos tienen que servir para cualquier pp.

Ese pp no es el más chico que sirve. Es el que la demostración garantiza. Para 0n1n\mathtt{0}^n\mathtt{1}^n alcanza con p=2p = 2: toda cadena 0n1n\mathtt{0}^n\mathtt{1}^n con n≥1n \geq 1 se divide con v=0v = \mathtt{0} el último cero, x=εx = \varepsilon e y=1y = \mathtt{1} el primer uno.

El árbol más pequeño hace falta. Sin esa elección, la condición 2 puede fallar: una gramática con reglas como A→BA \to B y B→AB \to A tiene árboles con caminos larguísimos que no agregan ningún símbolo, y la repetición encontrada podría tener v=y=εv = y = \varepsilon. El árbol con menos nodos no tiene vueltas inútiles.

Error común. Leer el lema al revés. Dice que si un lenguaje es libre de contexto, entonces sus cadenas largas se pueden bombear. No dice que un lenguaje cuyas cadenas se pueden bombear sea libre de contexto: hay lenguajes que cumplen las tres condiciones y no lo son. El lema solo sirve para demostrar que un lenguaje no es libre de contexto.

Usar el lema: el juego

Para demostrar que un lenguaje AA no es libre de contexto se razona por contradicción: suponemos que lo es, y entonces el lema vale para AA con algún pp que no conocemos. Como en la semana 4, conviene pensarlo como un juego contra un adversario que defiende que AA sí es libre de contexto.

  1. El adversario elige pp. No sabemos cuál: el argumento debe servir para todos.
  2. Nosotros elegimos la cadena ss, con s∈As \in A y ∣s∣≥p|s| \geq p. Puede depender de pp, y casi siempre depende.
  3. El adversario elige la división s=uvxyzs = uvxyz, con ∣vy∣>0|vy| > 0 y ∣vxy∣≤p|vxy| \leq p. No sabemos cuál: el argumento debe servir para todas. Aquí está el análisis por casos.
  4. Nosotros elegimos el exponente ii, y ganamos si uvixyiz∉Auv^ixy^iz \notin A. Puede ser un ii distinto en cada caso.

Si ganamos siempre, la condición 1 del lema falla para esa ss, y AA no es libre de contexto.

Lo difícil es el paso 3. Con los regulares, la condición ∣xy∣≤p|xy| \leq p clavaba la parte repetida al principio de la cadena. Aquí la ventana vxyvxy puede estar en cualquier lugar, y dentro de ella vv e yy pueden caer de muchas maneras. La demostración tiene que cubrirlas todas, y la manera de no olvidar ninguna es clasificarlas con un criterio que no deje huecos.

En los tres ejemplos que siguen, las cadenas están formadas por bloques de un mismo símbolo. Un trozo vv o yy puede estar dentro de un solo bloque, y entonces es de un solo tipo de símbolo, o puede abarcar el borde entre dos bloques, y entonces tiene dos símbolos distintos. Esos dos casos se comportan muy distinto al bombear, y el segundo es el que se olvida.

El lenguaje aⁿbⁿcⁿ

Afirmación. D={ anbncn:n≥0 }D = \{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\} no es libre de contexto.

Demostración. Por contradicción, con el lema de bombeo. Supongamos que DD es libre de contexto, y sea pp su longitud de bombeo.

Nuestra cadena: s=apbpcps = \mathtt{a}^p\mathtt{b}^p\mathtt{c}^p. Está en DD y ∣s∣=3p≥p|s| = 3p \geq p.

La división del adversario: cualquier s=uvxyzs = uvxyz con ∣vy∣>0|vy| > 0 y ∣vxy∣≤p|vxy| \leq p. Elegimos i=2i = 2 en todos los casos, y mostramos que s′=uv2xy2z∉Ds' = uv^2xy^2z \notin D. Hay dos casos, que entre los dos cubren todas las divisiones.

Caso 1: vv e yy tienen, cada una, un solo tipo de símbolo (o son vacías; las dos no). Entonces v2v^2 sigue dentro del bloque de vv, y lo mismo y2y^2: s′s' tiene todavía la forma a∗b∗c∗\mathtt{a}^*\mathtt{b}^*\mathtt{c}^*, con los bloques en orden. Pero entre vv e yy tocan a lo sumo dos de los tres símbolos. Al pasar de ss a s′s', la cantidad de al menos uno de los tres símbolos crece, porque ∣vy∣>0|vy| > 0, y la de al menos uno queda en pp. Las tres cantidades no pueden ser iguales, y s′∉Ds' \notin D.

Caso 2: vv o yy tiene dos símbolos distintos. Digamos que es vv; con yy es igual. Como vv es un trozo de apbpcp\mathtt{a}^p\mathtt{b}^p\mathtt{c}^p, sus símbolos están en orden: tiene una a\mathtt{a} antes de una b\mathtt{b}, o una b\mathtt{b} antes de una c\mathtt{c}. En v2=vvv^2 = vv, la segunda copia empieza después de que la primera terminó. Si v=ajbkv = \mathtt{a}^j\mathtt{b}^k con j,k≥1j, k \geq 1, entonces vv=ajbkajbkvv = \mathtt{a}^j\mathtt{b}^k\mathtt{a}^j\mathtt{b}^k tiene una a\mathtt{a} después de una b\mathtt{b}. En general, s′s' tiene dos símbolos fuera de orden, no es de la forma a∗b∗c∗\mathtt{a}^*\mathtt{b}^*\mathtt{c}^*, y s′∉Ds' \notin D.

En los dos casos s′∉Ds' \notin D, contra la condición 1 del lema. Luego DD no es libre de contexto. ∎

Error común. Olvidar el caso 2. La demostración incompleta dice ”vv e yy tocan a lo sumo dos de los tres símbolos, así que al bombear una cantidad queda atrás”, y eso supone sin decirlo que vv e yy son de un solo tipo. Si v=abv = \mathtt{ab}, bombear no “agrega una a\mathtt{a} y una b\mathtt{b}” a sus bloques: mete una a\mathtt{a} en medio de las b\mathtt{b}. El resultado tampoco está en el lenguaje, pero por otra razón, y hay que decirla. Cada vez que escriban “la cantidad de tal símbolo crece”, pregúntense si antes mostraron que la cadena sigue ordenada.

En este ejemplo no usamos la condición 3, ∣vxy∣≤p|vxy| \leq p. Con ella, el caso 1 se puede decir de otro modo: entre la última a\mathtt{a} y la primera c\mathtt{c} hay pp símbolos b\mathtt{b}, así que una ventana de longitud pp no puede tocar a la vez una a\mathtt{a} y una c\mathtt{c}. En los dos ejemplos siguientes la condición 3 es indispensable.

El lenguaje ww

Sea E={ ww:w∈{0,1}∗ }E = \{\, ww : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\}, las cadenas que son una mitad repetida: 0101\mathtt{0101}, 1111\mathtt{1111}, 011011\mathtt{011011}. Se parece mucho a los palíndromos wwRww^R, que sí son libres de contexto. La diferencia es el orden de la segunda mitad. Una pila devuelve lo guardado al revés, que es lo que piden los palíndromos y justo lo contrario de lo que pide wwww.

Un intento que falla. La cadena más simple de EE que depende de pp es s=0p10p1s = \mathtt{0}^p\mathtt{1} \mathtt{0}^p\mathtt{1}. Con ella perdemos el juego. El adversario divide así:

u=0p−1,v=0,x=1,y=0,z=0p−11.u = \mathtt{0}^{p-1}, \quad v = \mathtt{0}, \quad x = \mathtt{1}, \quad y = \mathtt{0}, \quad z = \mathtt{0}^{p-1}\mathtt{1}.

Cumple las condiciones: ∣vy∣=2|vy| = 2 y ∣vxy∣=3≤p|vxy| = 3 \leq p si p≥3p \geq 3. Y para todo ii,

uvixyiz=0p−1+i 1 0i+p−1 1,uv^ixy^iz = \mathtt{0}^{p-1+i}\,\mathtt{1}\,\mathtt{0}^{i+p-1}\,\mathtt{1},

que es wwww con w=0p−1+i1w = \mathtt{0}^{p-1+i}\mathtt{1}. El adversario puso vv e yy a los dos lados del 1\mathtt{1} del medio, y al bombear las dos mitades crecen juntas. Esto no dice que EE sea libre de contexto: dice que esta ss no sirve. La elección de la cadena es parte de la demostración.

Lo que falló es que los ceros de la primera mitad y los de la segunda estaban pegados, separados por un solo símbolo. Hay que alejarlos más de pp.

Afirmación. E={ ww:w∈{0,1}∗ }E = \{\, ww : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\} no es libre de contexto.

Demostración. Por contradicción, con el lema de bombeo. Supongamos que EE es libre de contexto, y sea pp su longitud de bombeo.

Nuestra cadena: s=0p1p0p1ps = \mathtt{0}^p\mathtt{1}^p\mathtt{0}^p\mathtt{1}^p. Está en EE, con w=0p1pw = \mathtt{0}^p\mathtt{1}^p, y ∣s∣=4p≥p|s| = 4p \geq p. Tiene cuatro bloques de longitud pp, que numeramos del 1 al 4. Los bloques 1 y 3 son de ceros y los bloques 2 y 4 de unos.

Antes de jugar, un lema que dice cuándo una cadena de cuatro bloques está en EE.

Lema (de los cuatro bloques). Sea t=0a1b0c1dt = \mathtt{0}^a\mathtt{1}^b\mathtt{0}^c\mathtt{1}^d con a,b,c,d≥1a, b, c, d \geq 1. Si t∈Et \in E, entonces a=ca = c y b=db = d.

Demostración del lema. Sea t=wwt = ww. Llamemos cambio a una posición de una cadena donde un símbolo es distinto del anterior. La cadena tt tiene exactamente 3 cambios, uno en cada borde entre bloques. Por otro lado, ww empieza con el primer símbolo de tt, que es 0\mathtt{0}, y termina con el último, que es 1\mathtt{1}. Si ww tiene mm cambios, entonces wwww tiene 2m+12m + 1: los de cada copia, más uno en la unión, donde el 1\mathtt{1} final de la primera copia se encuentra con el 0\mathtt{0} inicial de la segunda. De 2m+1=32m + 1 = 3 sale m=1m = 1. Una cadena que empieza con 0\mathtt{0}, termina con 1\mathtt{1} y tiene un solo cambio es 0e1f\mathtt{0}^e\mathtt{1}^f con e,f≥1e, f \geq 1. Entonces t=0e1f0e1ft = \mathtt{0}^e\mathtt{1}^f\mathtt{0}^e \mathtt{1}^f, y como una cadena se parte en bloques de una sola manera, a=c=ea = c = e y b=d=fb = d = f. ∎

La división del adversario: cualquier s=uvxyzs = uvxyz con ∣vy∣>0|vy| > 0 y ∣vxy∣≤p|vxy| \leq p.

Lo que da la condición 3. La ventana vxyvxy mide a lo sumo pp, y cada bloque mide pp. Para tocar dos bloques que no son vecinos, la ventana tendría que contener entero el bloque que hay entre ellos, y además un símbolo de cada lado: al menos p+2p + 2 símbolos. Así que vxyvxy toca un solo bloque, o dos bloques vecinos. Dos bloques del mismo símbolo, el 1 y el 3 o el 2 y el 4, nunca son vecinos. Llamemos pareja de un bloque al otro bloque del mismo símbolo. Entonces: si vxyvxy toca un bloque, no toca a su pareja.

Hay dos casos, que entre los dos cubren todas las divisiones.

Caso 1: vv e yy tienen, cada una, un solo tipo de símbolo (o son vacías; las dos no). Elegimos i=2i = 2. Cada una está dentro de un bloque, y al duplicarla ese bloque crece. Entonces s′=uv2xy2z=0a1b0c1ds' = uv^2xy^2z = \mathtt{0}^a\mathtt{1}^b\mathtt{0}^c\mathtt{1}^d, donde cada exponente es pp o más, y al menos uno es mayor que pp porque ∣vy∣>0|vy| > 0. El bloque que creció tiene a su pareja intacta, de longitud pp, porque la ventana no la toca. Entonces a≠ca \neq c o b≠db \neq d, y por el lema de los cuatro bloques, s′∉Es' \notin E.

Caso 2: vv o yy tiene dos símbolos distintos, es decir, abarca el borde entre dos bloques vecinos. Aquí i=2i = 2 desordenaría la cadena, como en el ejemplo anterior. Elegimos i=0i = 0: borrar no desordena. Digamos que es vv la que abarca el borde entre un bloque y el siguiente; con yy es igual. Entonces vv tiene al menos un símbolo de cada uno de esos dos bloques, y toda la ventana vxyvxy está dentro de ellos. Al borrar vv e yy:

  • los dos bloques que la ventana no toca siguen midiendo pp;
  • cada uno de los dos bloques tocados pierde al menos un símbolo;
  • ninguno de los dos queda vacío. Entre vv e yy se borran a lo sumo ∣vy∣≤p|vy| \leq p símbolos, repartidos entre los dos bloques con al menos uno de cada uno. Así que de cada bloque se borran a lo sumo p−1p - 1.

Entonces s′=uxz=0a1b0c1ds' = uxz = \mathtt{0}^a\mathtt{1}^b\mathtt{0}^c\mathtt{1}^d con a,b,c,d≥1a, b, c, d \geq 1, donde los dos bloques tocados miden menos de pp y sus parejas miden pp. Otra vez a≠ca \neq c o b≠db \neq d, y por el lema, s′∉Es' \notin E.

En los dos casos hay un exponente que saca la cadena de EE, contra la condición 1. Luego EE no es libre de contexto. ∎

Dos comentarios. Primero, la condición 3 fue esencial: sin ella, el adversario podría poner vv en el bloque 1 e yy en el bloque 3 y hacer crecer los dos juntos, como hizo con la primera cadena. La cadena de cuatro bloques largos está elegida para que la ventana no llegue de un bloque a su pareja. Segundo, cada caso usó un exponente distinto, y por una razón: en el caso 1, i=2i = 2 mantiene los cuatro bloques y el lema se aplica directo; en el caso 2, i=2i = 2 produciría una cadena de seis bloques, de la que el lema no dice nada, y con i=0i = 0 se queda en cuatro.

El lenguaje aⁱbʲcᵏ con i ≤ j ≤ k

Sea H={ aibjck:i≤j≤k }H = \{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i \leq j \leq k \,\}. Está en HH toda cadena de DD, y muchas más: abbccc\mathtt{abbccc}, bc\mathtt{bc}, ccc\mathtt{ccc}. Este ejemplo enseña algo que los anteriores no: a veces hay que bombear hacia abajo.

Un intento que falla. Con s=apbpcps = \mathtt{a}^p\mathtt{b}^p\mathtt{c}^p y i=2i = 2 siempre, como en el primer ejemplo, el adversario gana: pone vv e yy dentro de las c\mathtt{c}. Al bombear hacia arriba hay más c\mathtt{c}, y p≤p≤p+∣vy∣p \leq p \leq p + |vy|: la cadena sigue en el lenguaje. Las desigualdades de HH toleran que crezca lo de la derecha. Lo que no toleran es que disminuya.

Afirmación. H={ aibjck:i≤j≤k }H = \{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i \leq j \leq k \,\} no es libre de contexto.

Demostración. Por contradicción, con el lema de bombeo. Supongamos que HH es libre de contexto, y sea pp su longitud de bombeo.

Nuestra cadena: s=apbpcps = \mathtt{a}^p\mathtt{b}^p\mathtt{c}^p. Está en HH, porque p≤p≤pp \leq p \leq p, y ∣s∣=3p≥p|s| = 3p \geq p.

La división del adversario: cualquier s=uvxyzs = uvxyz con ∣vy∣>0|vy| > 0 y ∣vxy∣≤p|vxy| \leq p. Tres casos, que cubren todas las divisiones: o alguna de las dos abarca un borde (caso 1), o ninguna lo hace, y entonces en vyvy no hay ninguna a\mathtt{a} (caso 2) o hay alguna (caso 3).

Caso 1: vv o yy tiene dos símbolos distintos. Elegimos i=2i = 2. Como en el primer ejemplo, uv2xy2zuv^2xy^2z tiene dos símbolos fuera de orden y no es de la forma a∗b∗c∗\mathtt{a}^*\mathtt{b}^*\mathtt{c}^*. No está en HH.

En los casos 2 y 3, vv e yy tienen cada una un solo tipo de símbolo, así que bombear, hacia arriba o hacia abajo, solo cambia las longitudes de los bloques. La cadena que resulta sigue siendo de la forma a∗b∗c∗\mathtt{a}^*\mathtt{b}^*\mathtt{c}^*, y está en HH solo si no tiene más a\mathtt{a} que b\mathtt{b} ni más b\mathtt{b} que c\mathtt{c}. Entre vv e yy tocan a lo sumo dos de los tres símbolos.

Caso 2: en vyvy no hay ninguna a\mathtt{a}. Elegimos i=0i = 0. En uxzuxz sigue habiendo pp símbolos a\mathtt{a}, y se borró al menos una b\mathtt{b} o al menos una c\mathtt{c}. Si se borró alguna b\mathtt{b}, quedan menos de pp: hay más a\mathtt{a} que b\mathtt{b}. Si no se borró ninguna b\mathtt{b}, hay pp símbolos b\mathtt{b} y menos de pp símbolos c\mathtt{c}: hay más b\mathtt{b} que c\mathtt{c}. En cualquiera de los dos, uxz∉Huxz \notin H.

Caso 3: en vyvy hay alguna a\mathtt{a}. Elegimos i=2i = 2. En uv2xy2zuv^2xy^2z hay más de pp símbolos a\mathtt{a}. Como vv e yy tocan a lo sumo dos símbolos y uno es la a\mathtt{a}, no tocan las b\mathtt{b} o no tocan las c\mathtt{c}. Si no tocan las b\mathtt{b}, hay pp símbolos b\mathtt{b} y más a\mathtt{a} que b\mathtt{b}. Si no tocan las c\mathtt{c}, hay pp símbolos c\mathtt{c} y más a\mathtt{a} que c\mathtt{c}, y eso tampoco puede pasar en HH: si las a\mathtt{a} no son más que las b\mathtt{b}, ni las b\mathtt{b} más que las c\mathtt{c}, las a\mathtt{a} no son más que las c\mathtt{c}. En cualquiera de los dos, uv2xy2z∉Huv^2xy^2z \notin H.

En los tres casos hay un exponente que saca la cadena de HH. Luego HH no es libre de contexto. ∎

Esta demostración, tal como está escrita, no usó la condición 3. Con ella, el caso 3 se simplifica: una ventana de longitud pp que toca una a\mathtt{a} no llega a ninguna c\mathtt{c}.

El juego, jugado por la computadora

Para una cadena concreta y un pp concreto, las divisiones que el adversario puede elegir son una cantidad finita, y un programa puede probarlas todas. El programa pump_demo lo hace para los ejemplos de esta sección, con pp de 1 a 6: lista todas las divisiones con ∣vy∣>0|vy| > 0 y ∣vxy∣≤p|vxy| \leq p, y cuenta cuántas salen del lenguaje con i=2i = 2, cuántas siguen dentro con i=2i = 2 pero salen con i=0i = 0, y cuántas sobreviven, es decir, siguen dentro con todos los exponentes de 0 a 4.

$ build/pump_demo
{ 0^n 1^n },  s = 0^p 1^p  (libre de contexto: tiene que haber divisiones que sobreviven)
   p   |s|  divisiones  fuera con i=2  solo con i=0  sobreviven
   1     2           4              4             0           0
   2     4          23             22             0           1
   3     6          73             70             0           3
   4     8         175            168             0           7
   5    10         355            342             0          13
   6    12         644            622             0          22
  una división que sobrevive con p = 6: u = 0, v = 0, x = 0000, y = 1, z = 11111

{ a^n b^n c^n },  s = a^p b^p c^p
   p   |s|  divisiones  fuera con i=2  solo con i=0  sobreviven
   1     3           6              6             0           0
   2     6          37             37             0           0
   3     9         121            121             0           0
   4    12         295            295             0           0
   5    15         605            605             0           0
   6    18        1106           1106             0           0

{ ww },  s = 0^p 1 0^p 1  (una mala elección)
   p   |s|  divisiones  fuera con i=2  solo con i=0  sobreviven
   1     4           8              8             0           0
   2     6          37             37             0           0
   3     8         105            104             0           1
   4    10         235            232             0           3
   5    12         455            448             0           7
   6    14         798            785             0          13
  una división que sobrevive con p = 6: u = 00, v = 0, x = 0001, y = 0, z = 000001

{ ww },  s = 0^p 1^p 0^p 1^p
   p   |s|  divisiones  fuera con i=2  solo con i=0  sobreviven
   1     4           8              8             0           0
   2     8          51             51             0           0
   3    12         169            169             0           0
   4    16         415            415             0           0
   5    20         855            855             0           0
   6    24        1568           1568             0           0

{ a^i b^j c^k : i ≤ j ≤ k },  s = a^p b^p c^p
   p   |s|  divisiones  fuera con i=2  solo con i=0  sobreviven
   1     3           6              4             2           0
   2     6          37             26            11           0
   3     9         121             88            33           0
   4    12         295            219            76           0
   5    15         605            456           149           0
   6    18        1106            843           263           0

La tabla cuenta lo mismo que las demostraciones.

  • Con 0n1n\mathtt{0}^n\mathtt{1}^n, que sí es libre de contexto, desde p=2p = 2 hay divisiones que sobreviven, como exige el lema. La que muestra el programa tiene una vv en los ceros y una yy en los unos.
  • Con apbpcp\mathtt{a}^p\mathtt{b}^p\mathtt{c}^p contra DD, las 1106 divisiones de p=6p = 6 caen con i=2i = 2: los dos casos de la demostración usaban ese exponente.
  • Con la mala elección para wwww, desde p=3p = 3 hay divisiones que sobreviven. Una es la que encontramos a mano, con vv e yy a los lados del 1\mathtt{1} del medio; la que imprime el programa es otra del mismo estilo, con la yy más lejos.
  • Con la buena elección para wwww, no sobrevive ninguna. La tabla dice además que todas caen con i=2i = 2: en el caso 2 de la demostración también habría servido bombear hacia arriba. Elegimos i=0i = 0 porque con cuatro bloques el argumento es más corto, no porque fuera la única opción.
  • Con HH, la columna “solo con i=0” no es cero: 263 de las 1106 divisiones de p=6p = 6 siguen en el lenguaje al bombear hacia arriba, y solo se las derrota hacia abajo. Son las del caso 2.

El programa no demuestra nada sobre el lenguaje: prueba algunos pp, y la demostración tiene que valer para todos. Sirve para lo contrario, para encontrar errores: si un análisis por casos olvida una división, o le asigna el exponente equivocado, el programa la encuentra. test_pumping recorre así, división por división y con pp de 1 a 7, los casos de las tres demostraciones de esta sección, cada uno con el exponente que la demostración dice.

Propiedades de cierre

Con los regulares, las propiedades de cierre eran todas buenas noticias: unión, intersección, complemento, concatenación y estrella. Con los libres de contexto, tres se conservan y dos se pierden.

Unión, concatenación y estrella: sí

Las tres se demuestran con gramáticas, y son las construcciones para “unir gramáticas” de la semana 5.

Teorema. Si A1A_1 y A2A_2 son libres de contexto, también lo son A1∪A2A_1 \cup A_2, A1A2A_1A_2 y A1∗A_1^*.

Demostración. Por construcción. Sean G1=(V1,Σ,R1,S1)G_1 = (V_1, \Sigma, R_1, S_1) y G2=(V2,Σ,R2,S2)G_2 = (V_2, \Sigma, R_2, S_2) gramáticas de A1A_1 y A2A_2. Primero se cambian los nombres de las variables para que V1V_1 y V2V_2 no tengan ninguna en común. Sea SS una variable nueva. En los tres casos la gramática nueva tiene todas las variables y todas las reglas de las originales, la variable inicial SS, y además:

Lenguaje Reglas nuevas
A1∪A2A_1 \cup A_2 S→S1∣S2S \to S_1 \mid S_2
A1A2A_1A_2 S→S1S2S \to S_1S_2
A1∗A_1^* S→S1S∣εS \to S_1S \mid \varepsilon (aquí solo se usa G1G_1)

Por qué funcionan. La clave es que las variables de G1G_1 solo aparecen en reglas de G1G_1, y las de G2G_2 en las de G2G_2: una vez que la derivación entra a S1S_1, todo lo que salga de ahí es una derivación de G1G_1.

  • Unión. Toda derivación empieza con S⇒S1S \Rightarrow S_1 o con S⇒S2S \Rightarrow S_2 y sigue dentro de una sola gramática. Así que S⇒∗wS \Rightarrow^* w si y solo si S1⇒∗wS_1 \Rightarrow^* w o S2⇒∗wS_2 \Rightarrow^* w.
  • Concatenación. Toda derivación empieza con S⇒S1S2S \Rightarrow S_1S_2. Lo que deriva S1S_1 y lo que deriva S2S_2 no se mezclan, así que la cadena final es w1w2w_1w_2 con S1⇒∗w1S_1 \Rightarrow^* w_1 y S2⇒∗w2S_2 \Rightarrow^* w_2. Y al revés, cualquier w1w2w_1w_2 así se deriva.
  • Estrella. Usando nn veces la regla S→S1SS \to S_1S y después S→εS \to \varepsilon se obtiene S⇒∗S1nS \Rightarrow^* S_1^n, y de ahí cualquier concatenación de nn cadenas de A1A_1. Por inducción sobre la cantidad de usos de S→S1SS \to S_1S, no se obtiene nada más. ∎

Error común. Juntar las reglas de dos gramáticas sin cambiar los nombres. Si G1G_1 es S→aAS \to \mathtt{a}A, A→bA \to \mathtt{b} y G2G_2 es S→cAS \to \mathtt{c}A, A→dA \to \mathtt{d}, cada una genera una sola cadena: ab\mathtt{ab} y cd\mathtt{cd}. Mezcladas, la variable AA tiene las dos reglas, y la “unión” genera también ad\mathtt{ad} y cb\mathtt{cb}.

Intersección y complemento: no

Teorema. Los lenguajes libres de contexto no son cerrados bajo intersección ni bajo complemento.

Demostración. Con un contraejemplo. Sean

A={ anbncm:n,m≥0 }B={ ambncn:n,m≥0 }.A = \{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^m : n, m \geq 0 \,\} \qquad B = \{\, \mathtt{a}^m\mathtt{b}^n\mathtt{c}^n : n, m \geq 0 \,\}.

Los dos son libres de contexto. AA es lo que reconocía el intento fallido de machines/anbn_cm.pda, y es la concatenación de {anbn}\{\mathtt{a}^n\mathtt{b}^n\} con c∗\mathtt{c}^*. BB es la concatenación de a∗\mathtt{a}^* con {bncn}\{\mathtt{b}^n\mathtt{c}^n\}. Sus gramáticas están en machines/anbn_cm.cfg y machines/am_bncn.cfg:

A:S→XCX→aXb∣εC→cC∣εB:S→AYA→aA∣εY→bYc∣ε\begin{aligned} A&: & S &\to XC & X &\to \mathtt{a}X\mathtt{b} \mid \varepsilon & C &\to \mathtt{c}C \mid \varepsilon \\ B&: & S &\to AY & A &\to \mathtt{a}A \mid \varepsilon & Y &\to \mathtt{b}Y\mathtt{c} \mid \varepsilon \end{aligned}

Una cadena está en A∩BA \cap B si tiene la forma aibjck\mathtt{a}^i\mathtt{b}^j\mathtt{c}^k con i=ji = j, por estar en AA, y con j=kj = k, por estar en BB. Entonces

A∩B={ anbncn:n≥0 }=D,A \cap B = \{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\} = D,

que no es libre de contexto. La intersección de dos lenguajes libres de contexto puede no serlo.

Para el complemento, por contradicción. Si la clase fuera cerrada bajo complemento, como lo es bajo unión, también lo sería bajo intersección, por la ley de De Morgan:

A∩B= A‾∪B‾ ‾.A \cap B = \overline{\,\overline{A} \cup \overline{B}\,}.

Y acabamos de ver que no lo es. ∎

$ build/cfg_strings machines/anbn_cm.cfg 5
12 cadenas de longitud a lo sumo 5:
  ε c ab cc abc ccc aabb abcc cccc aabbc abccc ccccc
$ build/cfg_strings machines/am_bncn.cfg 5
12 cadenas de longitud a lo sumo 5:
  ε a aa bc aaa abc aaaa aabc bbcc aaaaa aaabc abbcc

Las únicas cadenas que están en las dos listas son ε\varepsilon y abc\mathtt{abc}.

Vale la pena entender por qué la construcción del producto de la semana 1 no se puede repetir. Con dos DFA, la máquina producto llevaba un par de estados. Con dos PDA habría que llevar un par de estados y dos pilas, y un PDA tiene una sola. Es el mismo error común de la sesión A, visto desde otro lado: AA necesita la pila para comparar las a\mathtt{a} con las b\mathtt{b}, BB la necesita para las b\mathtt{b} con las c\mathtt{c}, y no hay manera de hacer las dos cosas con una. Una máquina con dos pilas es otro modelo, mucho más poderoso: es equivalente a la máquina de Turing de la semana próxima.

El argumento del complemento no dice cuál lenguaje libre de contexto tiene un complemento que no lo es. Un ejemplo concreto: el complemento de DD sí es libre de contexto (es el ejercicio 9), y su complemento es DD.

Intersección con un lenguaje regular: sí

Hay una versión débil de la intersección que sí se conserva, y es la que más se usa.

Teorema. Si AA es libre de contexto y BB es regular, entonces A∩BA \cap B es libre de contexto.

Demostración. Por construcción: el producto de un PDA con un DFA. Ahora hay una sola pila, la del PDA, y el DFA solo agrega un estado.

Qué se construye. Sean P=(QP,Σ,Γ,δP,p0,FP)P = (Q_P, \Sigma, \Gamma, \delta_P, p_0, F_P) un PDA de AA y M=(QM,Σ,δM,m0,FM)M = (Q_M, \Sigma, \delta_M, m_0, F_M) un DFA de BB. El PDA producto tiene los estados QP×QMQ_P \times Q_M, el mismo alfabeto de pila Γ\Gamma, el estado inicial (p0,m0)(p_0, m_0) y los estados de aceptación FP×FMF_P \times F_M. Sus transiciones copian las de PP, y la segunda coordenada sigue al DFA:

  • por cada transición de PP que lee un símbolo aa, (p′,c)∈δP(p,a,b)(p', c) \in \delta_P(p, a, b), y cada m∈QMm \in Q_M: de (p,m)(p, m) a (p′,δM(m,a))(p', \delta_M(m, a)), con la misma etiqueta a,b→ca, b \to c;
  • por cada transición de PP que no lee, (p′,c)∈δP(p,ε,b)(p', c) \in \delta_P(p, \varepsilon, b), y cada m∈QMm \in Q_M: de (p,m)(p, m) a (p′,m)(p', m), con la etiqueta ε,b→c\varepsilon, b \to c. El DFA no se mueve.

Por qué reconoce A∩BA \cap B. Por inducción sobre la cantidad de pasos se comprueba que el producto llega a la configuración ((p,m),y,γ)((p, m), y, \gamma) habiendo leído xx si y solo si PP llega a (p,y,γ)(p, y, \gamma) habiendo leído xx y además δM∗(m0,x)=m\delta_M^*(m_0, x) = m: cada paso del producto es un paso de PP, y el DFA avanza exactamente cuando se lee un símbolo. Entonces el producto acepta ww si y solo si alguna ejecución de PP con ww termina en FPF_P y δM∗(m0,w)∈FM\delta_M^*(m_0, w) \in F_M: si y solo si w∈Aw \in A y w∈Bw \in B. ∎

El uso principal de este teorema es simplificar un lenguaje antes de aplicarle el lema de bombeo.

Ejemplo. Sea KK el lenguaje de las cadenas sobre {a,b,c}\{\mathtt{a}, \mathtt{b}, \mathtt{c}\} con la misma cantidad de a\mathtt{a}, de b\mathtt{b} y de c\mathtt{c}, en cualquier orden. Aplicar el lema directamente es incómodo, porque las cadenas de KK no tienen forma. Pero a∗b∗c∗\mathtt{a}^*\mathtt{b}^*\mathtt{c}^* es regular, y

K∩a∗b∗c∗={ anbncn }=D.K \cap \mathtt{a}^*\mathtt{b}^*\mathtt{c}^* = \{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n \,\} = D.

Si KK fuera libre de contexto, DD también lo sería, por el teorema. No lo es, así que KK tampoco. Comparen con el lenguaje de las cadenas con la misma cantidad de a\mathtt{a} que de b\mathtt{b}, que sí es libre de contexto: su PDA está en machines/equal_ab.pda. Otra vez, dos cantidades sí y tres no.

El mapa hasta ahora

Con esto termina la parte 2 del curso. Tenemos dos clases de lenguajes, una dentro de la otra, y para cada frontera un lenguaje concreto que la cruza.

Mapa de las clases de lenguajes como cajas una dentro de otra. La caja de afuera es todos los lenguajes. Dentro, la de los libres de contexto, con la nota gramáticas = autómatas de pila. Dentro de ella, la de los libres de contexto deterministas, los de los autómatas de pila deterministas. Y dentro, la de los regulares: DFA = NFA = expresiones regulares. En la caja de los regulares están a*b* y termina en 01. En la de los deterministas, fuera de los regulares, 0ⁿ1ⁿ y w#wᴿ. En la de los libres de contexto, fuera de los deterministas, wwᴿ, con la nota de que hay que adivinar el medio. Fuera de los libres de contexto, aⁿbⁿcⁿ y ww, con la nota de que ningún PDA los reconoce. Al pie: cada inclusión es estricta; 0ⁿ1ⁿ no es regular, wwᴿ no tiene PDA determinista, y aⁿbⁿcⁿ y ww no son libres de contexto, por el lema de bombeoMapa de las clases de lenguajes como cajas una dentro de otra. La caja de afuera es todos los lenguajes. Dentro, la de los libres de contexto, con la nota gramáticas = autómatas de pila. Dentro de ella, la de los libres de contexto deterministas, los de los autómatas de pila deterministas. Y dentro, la de los regulares: DFA = NFA = expresiones regulares. En la caja de los regulares están a*b* y termina en 01. En la de los deterministas, fuera de los regulares, 0ⁿ1ⁿ y w#wᴿ. En la de los libres de contexto, fuera de los deterministas, wwᴿ, con la nota de que hay que adivinar el medio. Fuera de los libres de contexto, aⁿbⁿcⁿ y ww, con la nota de que ningún PDA los reconoce. Al pie: cada inclusión es estricta; 0ⁿ1ⁿ no es regular, wwᴿ no tiene PDA determinista, y aⁿbⁿcⁿ y ww no son libres de contexto, por el lema de bombeo
El mapa al terminar la parte 2. Cada frontera tiene un lenguaje concreto que la cruza.
Clase Descripción Máquina Qué no puede Lenguaje que lo muestra
Regulares Expresión regular DFA, NFA Contar sin tope {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}
Libres de contexto Gramática PDA Comparar tres cantidades; repetir en el mismo orden {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\}, {ww}\{ww\}
Operación Regulares Libres de contexto
Unión, concatenación, estrella sí sí
Intersección sí no
Complemento sí no
Intersección con un regular sí sí
El no determinismo agrega poder no sí
Decidir si una cadena está tiempo lineal, con el DFA O(n3)O(n^3), con CYK

Las dos clases tienen su lema de bombeo, y los dos dicen lo mismo en el fondo: una máquina con una cantidad finita de piezas, sean estados o variables, que procesa algo muy largo, tiene que repetir alguna, y lo que pasa entre las dos repeticiones se puede repetir.

Los dos lenguajes que quedaron fuera, {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\} y {ww}\{ww\}, no son difíciles en ningún sentido práctico: un programa de diez líneas los decide. Lo que les falta a nuestras máquinas es poder volver sobre lo que guardaron sin destruirlo. La semana próxima le damos eso a la máquina, y el modelo que resulta, la máquina de Turing, ya no se queda corto frente a ningún programa.

Cómo trabaja un parser real

Esta sección es opcional (✂️).

Un compilador tiene que resolver todos los días el problema de esta semana: dada una gramática y un texto, decidir si el texto es del lenguaje y construir su árbol. No usa CYK, que cuesta O(n3)O(n^3) y sería inaceptable para un archivo de cien mil tokens. Tampoco usa la búsqueda de run_pda. Usa lo que la sección El PDA determinista reconoce menos anunció: una gramática elegida para que un autómata de pila determinista la reconozca, en tiempo lineal. El trabajo se hace en dos etapas, y las dos son temas de este curso.

El lexer: expresiones regulares

La primera etapa convierte los caracteres en tokens: números, nombres, operadores, paréntesis. Cada tipo de token se describe con una expresión regular, y reconocerlos es trabajo de un autómata finito, el de las semanas 1 a 3. Para las expresiones aritméticas alcanzan cinco:

Token Expresión regular
número [0-9]+
suma \+
producto \*
paréntesis \( y \)

El lexer de expr.h es ese autómata escrito a mano, con dos estados: fuera de un número y dentro de un número. Lee cada carácter una vez, salta los espacios y entrega la lista de tokens. La gramática ya no ve caracteres: su alfabeto son los tokens. Por eso machines/expr.cfg tiene un solo terminal, a\mathtt{a}, para “un número”.

El parser: una función por variable

La segunda etapa es la gramática. Con la de la semana 5, que no es ambigua:

E→E+T∣TT→T∗F∣FF→(E)∣nuˊmeroE \to E + T \mid T \qquad T \to T * F \mid F \qquad F \to \mathtt{(}E\mathtt{)} \mid \text{número}

Un parser descendente recursivo tiene una función por variable. La función de FF mira el token que viene: si es un número, lo consume; si es un paréntesis que abre, lo consume, llama a la función de EE y exige un paréntesis que cierra. Nunca tiene que adivinar entre sus dos reglas, porque el siguiente token decide.

Con EE y TT hay un obstáculo, que ya conocemos. La regla E→E+TE \to E + T es recursiva por la izquierda. Escrita tal cual, la función de EE empezaría llamándose a sí misma sin haber consumido nada, y no terminaría nunca: es el mismo ciclo que hacía crecer la pila del PDA con a+. La salida estándar es observar que las reglas de EE generan “un TT, seguido de cero o más veces + T+\,T”, y escribir eso como un ciclo:

// E → E + T | T, como un ciclo: un T, y después cero o más veces "+ T".
Parsed expression() {
    Parsed left = term();
    while (peek().kind == TokenKind::Plus) {
        next++;
        Parsed right = term();
        left = {left.value + right.value, "(" + left.tree + " + " + right.tree + ")"};
    }
    return left;
}

Es la función expression de expr.h, sin el contador de llamadas ni la comprobación de overflow. Cada vuelta del ciclo mete lo acumulado como hijo izquierdo de una suma nueva: agrupa hacia la izquierda, igual que el árbol de la regla E→E+TE \to E + T. La función de TT es idéntica, con el producto y con factor.

$ build/parse_expr '2 + 3 * 4' '(2 + 3) * 4' '2 + 3 + 4' '2 + * 3'
2 + 3 * 4
  tokens:  NUM(2) + NUM(3) * NUM(4)
  árbol:   (2 + (3 * 4))
  valor:   14
  5 tokens, 6 llamadas a las funciones del parser
(2 + 3) * 4
  tokens:  ( NUM(2) + NUM(3) ) * NUM(4)
  árbol:   ((2 + 3) * 4)
  valor:   20
  7 tokens, 9 llamadas a las funciones del parser
2 + 3 + 4
  tokens:  NUM(2) + NUM(3) + NUM(4)
  árbol:   ((2 + 3) + 4)
  valor:   9
  5 tokens, 7 llamadas a las funciones del parser
2 + * 3
  tokens:  NUM(2) + * NUM(3)
  error: columna 5: se esperaba un número o ( y llegó *

La precedencia del producto sobre la suma no está programada en ningún if. Sale de la forma de la gramática: expression llama a term, y term termina de juntar sus factores antes de devolver.

Por qué es lineal

La variable next, la posición del token que toca, solo avanza. No hay búsqueda ni vuelta atrás: cada token se mira una cantidad acotada de veces y se consume una. Las llamadas también se pueden contar. Para una expresión correcta son 3 por la expresión completa y por cada paréntesis que abre (una de expression, una de term y una de factor), más 2 por cada suma y 1 por cada producto. En 2 + 3 * 4 son 3+2+1=63 + 2 + 1 = 6, y en (2 + 3) * 4 son 3⋅2+2+1=93 \cdot 2 + 2 + 1 = 9, como dice la salida. El total nunca pasa de tres veces la cantidad de tokens. test_expr comprueba esa cuenta, y también que el parser acepta exactamente las cadenas de tokens que genera machines/expr.cfg, con todas las de longitud a lo sumo 6.

Este parser es un autómata de pila determinista. Su pila es la pila de llamadas de C++: cada llamada pendiente a expression, term o factor es un símbolo que dice qué falta reconocer, exactamente como la pila del PDA de una gramática guardaba lo que faltaba derivar. La diferencia con aquel PDA es que este no adivina la regla: la elige mirando un token.

En la práctica. En Introducción a la Programación terminaron el semestre escribiendo un intérprete de un lenguaje pequeño. Su primera mitad era esto: un lexer que partía el texto en tokens y un parser que armaba el árbol con una función por cada tipo de construcción. Lo que entonces fue una técnica de programación, ahora tiene nombre y teoría: los tokens son un lenguaje regular, la sintaxis es un lenguaje libre de contexto determinista, y el parser es su autómata de pila. GCC y Clang, y los compiladores de Go y de Rust, tienen parsers escritos así, a mano.

El código de la semana

code/week-06/
├── pda.h                 struct Pda, lectura del formato .pda, configuraciones y la búsqueda
├── cfg.h                 struct Cfg, lectura del formato .cfg, cadenas que genera una gramática
├── convert.h             de gramática a PDA, normalizar un PDA, de PDA a gramática
├── closure.h             unión, concatenación y estrella de gramáticas
├── pumping.h             todas las divisiones s = uvxyz de una cadena, y qué pasa al bombear
├── expr.h                lexer y parser descendente recursivo de expresiones (opcional)
├── predicates.h          los lenguajes del capítulo como funciones, para las pruebas
├── print.h               la tabla de una ejecución
├── show_pda.cpp          muestra un .pda como séxtupla
├── run_pda.cpp           simula un PDA y muestra una ejecución de aceptación
├── cfg_to_pda.cpp        la construcción de gramática a PDA
├── normalize_pda.cpp     normaliza un PDA
├── pda_to_cfg.cpp        la construcción de PDA a gramática
├── cfg_strings.cpp       las cadenas de una gramática hasta una longitud
├── pump_demo.cpp         el juego del lema de bombeo, con p pequeños
├── parse_expr.cpp        analiza y evalúa expresiones (opcional)
├── machines/             los autómatas (.pda) y las gramáticas (.cfg) del capítulo
├── errors/               dos descripciones que no son un PDA
├── test_pda.cpp          cada autómata contra una función; las ejecuciones de los apuntes
├── test_convert.cpp      las dos construcciones, la normalización y el cierre
├── test_pumping.cpp      los análisis por casos, división por división
├── test_expr.cpp         el parser contra la gramática
└── lab/pda_sim/          el laboratorio (opcional)

make compila todo, y make test corre las pruebas con ASan y UBSan. Las pruebas comprueban con assert lo que este capítulo afirma.

  • test_pda compara cada autómata de machines/ con una función de C++ que decide el mismo lenguaje mirando la cadena completa, sobre todas las cadenas hasta una longitud: 10 para los alfabetos de dos símbolos y 8 para los de tres. Comprueba además las ejecuciones copiadas en estos apuntes y los tres finales de la búsqueda.
  • test_convert comprueba, para siete gramáticas, que el PDA construido acepta exactamente lo que la gramática genera; para ocho autómatas, que la forma normalizada acepta lo mismo y con la pila vacía, y que la gramática de las ApqA_{pq} genera exactamente lo que el autómata acepta; y las construcciones de unión, concatenación y estrella. También que la intersección de los lenguajes de anbn_cm.cfg y am_bncn.cfg es {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\}.
  • test_pumping y test_expr son las pruebas de las secciones Usar el lema: el juego y Cómo trabaja un parser real.
$ make test
test_pda: ok (8 autómatas, 31964 cadenas en total)
test_convert: ok (7 gramáticas a PDA, 8 autómatas normalizados y pasados a gramática)
test_pumping: ok (13776 divisiones revisadas caso por caso)
test_expr: ok (19531 cadenas de tokens contra la gramática)
Todas las pruebas pasaron.

Las pruebas tardan bastante más que las de otras semanas, porque simulan decenas de miles de cadenas con los sanitizers activados.

Para saber qué cadenas genera una gramática sin depender del PDA, cfg.h las calcula por punto fijo: empieza con un conjunto vacío por variable y aplica las reglas hasta que ningún conjunto crece, guardando solo las cadenas de longitud a lo sumo nn. Es lento, pero vale para cualquier gramática.

Una de las siete gramáticas necesita un cuidado. El PDA de expr.cfg tiene configuraciones sin fin, como vimos, y la búsqueda no puede rechazar. Para esa gramática la prueba le pone a la búsqueda un tope de altura de pila: ∣w∣+1|w| + 1. Es correcto por una razón particular de esa gramática: no tiene reglas ε\varepsilon, así que cada símbolo de la pila va a generar al menos un terminal de lo que falta leer. Una configuración en qloopq_{\text{loop}} con más símbolos sobre la marca que símbolos por leer no puede llegar a aceptar, y descartarla no cambia la respuesta. Con ese tope las configuraciones son finitas.

Los archivos de machines/:

Archivo Lenguaje
zeros_ones.pda, zeros_ones.cfg {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}
zeros_ones_norm.pda el mismo, normalizado para pasar a gramática
balanced.pda, balanced.cfg paréntesis balanceados
even_palindromes.pda, even_palindromes.cfg {wwR}\{ww^R\}
equal_ab.pda, equal_ab.cfg igual cantidad de a\mathtt{a} que de b\mathtt{b}
ij_or_jk.pda {aibjck:i=j o j=k}\{\mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i = j \text{ o } j = k\}
anbn_cm.pda, anbn_cm.cfg {anbncm}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^m\}
am_bncn.cfg {ambncn}\{\mathtt{a}^m\mathtt{b}^n\mathtt{c}^n\}
even_ones.pda cantidad par de unos: un DFA escrito como PDA
expr.cfg expresiones aritméticas, sin ambigüedad

El laboratorio

La sesión de laboratorio de esta semana es para la práctica. El problema de lab/pda_sim queda como ejercicio opcional, con el juez de siempre.

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

Es un simulador: la entrada es un PDA en formato .pda seguido de una lista de cadenas, y la salida es acepta, rechaza o limite por cada una. El enunciado fija el límite en 10 000 configuraciones distintas y dice exactamente cuándo se responde cada cosa. pda.h ya trae una búsqueda, y pueden leerla. Como en la semana 1, solution.cpp se escribe sin incluirla. Lo que el laboratorio ejercita es lo de la sección Simular un PDA: buscar entre configuraciones: qué es una configuración, cuándo dos son la misma, y por qué hace falta recordar las vistas. Hay casos con ciclos de transiciones ε\varepsilon de los dos tipos, y casos donde una búsqueda en profundidad que no recuerda las configuraciones vistas tendría que recorrer 3303^{30} caminos.

Resumen

  • Un autómata de pila (PDA) es un NFA con una pila: memoria sin límite, pero solo se ve y se cambia la cima. Es P=(Q,Σ,Γ,δ,q0,F)P = (Q, \Sigma, \Gamma, \delta, q_0, F), con δ:Q×Σε×Γε→P(Q×Γε)\delta : Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \to \mathcal{P}(Q \times \Gamma_\varepsilon). Una transición “lee aa, saca bb, pone cc”, y cada uno puede ser ε\varepsilon.
  • Una configuración es (q,x,γ)(q, x, \gamma): estado, lo que falta leer y la pila. PP acepta ww si desde (q0,w,ε)(q_0, w, \varepsilon) llega a alguna configuración con toda la entrada leída y el estado en FF. Basta una ejecución, y la pila puede quedar con cualquier cosa.
  • La máquina no puede ver que la pila está vacía: se marca el fondo con un símbolo especial.
  • El no determinismo sirve para decidir algo que depende de lo que falta leer: dónde está el medio de un palíndromo, cuál de dos comparaciones hacer. Una pila compara una sola pareja de cantidades.
  • Simular un PDA es buscar en el grafo de configuraciones, recordando las vistas. La búsqueda puede no terminar si un ciclo de transiciones ε\varepsilon hace crecer la pila, y por eso lleva un límite.
  • De gramática a PDA: la pila guarda lo que falta derivar. Con una variable en la cima se la reemplaza por el lado derecho de una regla; con un terminal, se lo compara con la entrada.
  • De PDA a gramática: una variable ApqA_{pq} por cada par de estados, que genera las cadenas que llevan de pp a qq de pila vacía a pila vacía. Reglas Apq→aArsbA_{pq} \to aA_{rs}b, Apq→AprArqA_{pq} \to A_{pr}A_{rq} y App→εA_{pp} \to \varepsilon. Antes se normaliza el PDA: un solo estado de aceptación, pila vacía al aceptar, y cada transición pone o saca exactamente un símbolo.
  • Un lenguaje es libre de contexto si y solo si algún PDA lo reconoce. Todo lenguaje regular es libre de contexto.
  • Los PDA deterministas reconocen menos: {wwR}\{ww^R\} es libre de contexto y ninguno lo reconoce. A diferencia de los autómatas finitos, aquí el no determinismo agrega poder.
  • Lema de bombeo: si AA es libre de contexto, hay un pp tal que toda s∈As \in A con ∣s∣≥p|s| \geq p se divide en uvxyzuvxyz con uvixyiz∈Auv^ixy^iz \in A para todo i≥0i \geq 0, ∣vy∣>0|vy| > 0 y ∣vxy∣≤p|vxy| \leq p. Sale de un árbol de derivación alto, donde una variable se repite en un camino. Sirve p=b∣V∣+1p = b^{|V|+1}.
  • Para usarlo: elegir ss, y cubrir todas las divisiones, incluidas las que tienen vv o yy sobre el borde entre dos bloques. A veces hay que bombear hacia abajo, con i=0i = 0.
  • No son libres de contexto: {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\}, {ww}\{ww\} y {aibjck:i≤j≤k}\{\mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i \leq j \leq k\}.
  • Los lenguajes libres de contexto son cerrados bajo unión, concatenación y estrella, y bajo intersección con un lenguaje regular. No son cerrados bajo intersección ni bajo complemento.
  • ✂️ Un parser real tiene un lexer, que es un autómata finito, y un parser determinista, que lee cada token una vez. Un parser descendente recursivo tiene una función por variable, y su pila es la de llamadas.

Ejercicios

  1. Sigan a mano el autómata de machines/zeros_ones.pda con 000111\mathtt{000111} y con 0101\mathtt{0101}, escribiendo cada configuración. Comprueben con build/run_pda. ¿En qué configuración muere la ejecución de 0101\mathtt{0101}, y por qué no hay otra?
  2. Para el autómata de machines/even_palindromes.pda y la cadena 0000\mathtt{0000}, escriban todas las configuraciones alcanzables, agrupadas según después de cuántos símbolos salta la máquina de q1q_1 a q2q_2. ¿Cuántas son? ¿Cuál es la ejecución que acepta? Comparen con build/run_pda: la cantidad que imprime es la de las configuraciones descubiertas hasta encontrar la aceptación, que puede ser menor que el total.
  3. Diseñen un PDA para cada lenguaje, con una tabla de qué hace cada transición, y escríbanlo en formato .pda: (a) { anb2n:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^{2n} : n \geq 0 \,\}; (b) los palíndromos sobre {0,1}\{\mathtt{0}, \mathtt{1}\} de cualquier longitud, par o impar; (c) las cadenas sobre {a,b}\{\mathtt{a}, \mathtt{b}\} con más a\mathtt{a} que b\mathtt{b}. Pruébenlos con build/run_pda. En cada uno, digan dónde usa el no determinismo, o si es determinista.
  4. El autómata de machines/equal_ab.pda puede tener en la pila a\mathtt{a} y b\mathtt{b} mezcladas, porque con una a\mathtt{a} por leer y una b\mathtt{b} en la cima puede sacar o puede poner. Demuestren que aun así reconoce el lenguaje correcto: (a) si acepta ww, entonces ww tiene tantas a\mathtt{a} como b\mathtt{b}; (b) si ww tiene tantas a\mathtt{a} como b\mathtt{b}, la ejecución que saca siempre que puede acepta. Para (a), emparejen cada símbolo que se pone con el momento en que se saca.
  5. Apliquen la construcción de gramática a PDA a S→aSa∣bSb∣cS \to \mathtt{a}S\mathtt{a} \mid \mathtt{b}S\mathtt{b} \mid \mathtt{c}. Den los estados y las transiciones, y cuenten los estados con la fórmula del capítulo. Sigan la ejecución de aceptación de abcba\mathtt{abcba} y armen la tabla de “ya leído” y “pila” en las visitas a qloopq_{\text{loop}}. Comprueben con build/cfg_to_pda y build/run_pda.
  6. Consideren este PDA normalizado, con estado inicial q0q_0 y de aceptación q2q_2: de q0q_0 a q1q_1 con ε,ε→$\varepsilon, \varepsilon \to \texttt{\textdollar}; en q1q_1, (,ε→x\mathtt{(}, \varepsilon \to \mathtt{x} y ),x→ε\mathtt{)}, \mathtt{x} \to \varepsilon; de q1q_1 a q2q_2 con ε,$→ε\varepsilon, \texttt{\textdollar} \to \varepsilon. (a) ¿Qué lenguaje reconoce? (b) Den las reglas del tipo Apq→aArsbA_{pq} \to aA_{rs}b de su gramática. (c) Quiten las variables que no sirven y simplifiquen. ¿Qué gramática conocida queda? Aquí sí hace falta una regla del tipo Apq→AprArqA_{pq} \to A_{pr}A_{rq}: digan cuál y para qué cadena. Comprueben con build/pda_to_cfg.
  7. En la demostración de PDA a gramática, den un ejemplo de un PDA que cumple las condiciones 1 y 2 pero no la 3, y de una ejecución suya de pila vacía a pila vacía en la que el símbolo que se saca al final no es el que se puso al principio. ¿Qué paso del caso (a) deja de valer?
  8. Demuestren con el lema de bombeo que estos lenguajes no son libres de contexto, con el análisis por casos completo: (a) { anbnanbn:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{a}^n\mathtt{b}^n : n \geq 0 \,\}; (b) { aibjck:i<j<k }\{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i < j < k \,\}; (c) { w#w:w∈{0,1}∗ }\{\, w\mathtt{\#}w : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\}. En (b), ¿qué cadena eligen para que haga falta la menor cantidad de casos? Adapten pump_demo.cpp para comprobar su elección con pp pequeños.
  9. Demuestren que el complemento de D={anbncn}D = \{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\} es libre de contexto. Sugerencia: una cadena no está en DD si no es de la forma a∗b∗c∗\mathtt{a}^*\mathtt{b}^*\mathtt{c}^*, o si es aibjck\mathtt{a}^i\mathtt{b}^j\mathtt{c}^k con i≠ji \neq j, o con j≠kj \neq k. Escriban cada parte como un lenguaje libre de contexto y usen el cierre bajo unión. ¿Por qué esto no contradice que DD no sea libre de contexto?
  10. Usen el cierre bajo intersección con un lenguaje regular para demostrar que no son libres de contexto: (a) las cadenas sobre {a,b,c}\{\mathtt{a}, \mathtt{b}, \mathtt{c}\}, en cualquier orden, que no tienen más a\mathtt{a} que b\mathtt{b} ni más b\mathtt{b} que c\mathtt{c}; (b) { ww }\{\, ww \,\}, suponiendo ya demostrado que { 0a1b0a1b:a,b≥1 }\{\, \mathtt{0}^a\mathtt{1}^b\mathtt{0}^a\mathtt{1}^b : a, b \geq 1 \,\} no lo es. En cada caso digan con qué lenguaje regular intersecan, qué lenguaje queda y por qué es ese.
  11. ¿Verdadero o falso? Justifiquen con una demostración o un contraejemplo. (a) Si AA es libre de contexto y B⊆AB \subseteq A, entonces BB es libre de contexto. (b) Si AA es libre de contexto y BB es regular, entonces A−BA - B es libre de contexto. (c) Si AA y BB son libres de contexto, entonces A−BA - B lo es. (d) Si A∪BA \cup B es libre de contexto, entonces AA y BB lo son.
  12. Para programar. Agreguen a convert.h la construcción del producto de un PDA con un DFA, y escriban una prueba que la compare con la intersección calculada cadena por cadena. El DFA pueden leerlo con una copia de dfa.h de la semana 1. Úsenla con machines/equal_ab.pda y un DFA de a∗b∗\mathtt{a}^*\mathtt{b}^*: ¿qué lenguaje reconoce el producto?
  13. Para programar (✂️). Agreguen la resta y la división entera a expr.h, con la precedencia y la agrupación usuales: 8 - 3 - 2 vale 3, y no 7. Escriban primero la gramática sin ambigüedad. ¿Qué árbol arma su parser para 8 - 3 - 2, y qué pasaría si el ciclo agrupara hacia la derecha?