# Un simulador de PDA

Este problema es opcional: la sesión de laboratorio de la semana 6 es para la práctica. Vale la pena hacerlo
igual, porque es la primera vez que simulan una máquina **no determinista** que además tiene memoria sin límite.

El programa recibe la descripción de un autómata de pila (PDA) y una lista de cadenas, y dice por cada cadena
si el autómata la acepta.

Un PDA es $P = (Q, \Sigma, \Gamma, \delta, q_0, F)$. En cada instante está en una **configuración**: el estado,
cuántos símbolos de la entrada ya leyó, y el contenido de la pila. Empieza en el estado $q_0$, sin haber leído
nada y con la pila vacía. Una transición `p a b -> r c` se puede usar desde una configuración con estado $p$ si

- `a` es `eps`, o es el siguiente símbolo de la entrada, que entonces queda leído; y
- `b` es `eps`, o es el símbolo de la cima de la pila, que entonces se saca.

Después de usarla, el estado es $r$ y, si `c` no es `eps`, el símbolo `c` queda en la cima de la pila. Con la
pila vacía solo se pueden usar las transiciones que sacan `eps`.

El PDA **acepta** la cadena si alguna secuencia de transiciones lo lleva a una configuración con toda la
entrada leída y el estado en $F$. La pila no tiene que quedar vacía. Como desde una configuración puede haber
varias transiciones posibles, o ninguna, no basta con seguir un camino: hay que **buscar** entre todas las
configuraciones alcanzables.

## Entrada

La descripción de un PDA en el formato `.pda` de [`code/formats.md`](../../../formats.md), seguida del bloque
de cadenas del mismo documento:

```text
# { 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
strings: 4
0011

001
10
```

- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea anterior a
  `strings:`, también entre las transiciones.
- Puede haber líneas vacías antes de `delta:`. Entre `delta:` y `strings:` no hay líneas vacías.
- `states:`, `alphabet:`, `stack:`, `start:`, `accept:` y `delta:` vienen siempre en ese orden. `accept:` puede
  no tener ningún estado, y `stack:` puede no tener ningún símbolo.
- Después de `delta:` hay una transición por línea, `estado lee saca -> destino pone`, en cualquier orden.
  `lee` es un símbolo de `alphabet` o `eps`; `saca` y `pone` son un símbolo de `stack` o `eps`. Puede no haber
  ninguna transición, puede haber varias con el mismo lado izquierdo, y una misma línea puede estar repetida.
- `strings: k` dice cuántas cadenas siguen, una por línea. **Una línea vacía es la cadena vacía
  $\varepsilon$.** Después de `strings:` ya no hay comentarios.

## Salida

Una línea por cada cadena, en el mismo orden, con una de tres palabras. Sea $L = 10\,000$ el **límite de
configuraciones**.

- `acepta` si alguna configuración alcanzable desde la inicial es de aceptación.
- `rechaza` si ninguna lo es y las configuraciones alcanzables distintas son a lo sumo $L$.
- `limite` si ninguna lo es y las configuraciones alcanzables distintas son más de $L$.

Dos configuraciones son la misma si tienen el mismo estado, la misma posición en la entrada y la misma pila. La
configuración inicial cuenta.

En la práctica: su programa explora las configuraciones recordando las que ya vio. Si encuentra una de
aceptación, imprime `acepta` y pasa a la cadena siguiente. Si se le acaban las configuraciones por explorar,
imprime `rechaza`. Si llega a tener **más de $L$ configuraciones distintas** vistas sin haber aceptado, deja de
buscar e imprime `limite`. Con exactamente $L$ todavía no se detiene.

El límite existe porque un PDA puede tener un ciclo de transiciones `eps` que hace crecer la pila, como
`q eps eps -> q x`. Desde ahí hay infinitas configuraciones, una por cada altura de la pila, y una búsqueda
sin límite no terminaría nunca.

**Garantía.** En todos los casos del juez, una cadena que el autómata acepta tiene a lo sumo $L$
configuraciones alcanzables. Por eso la respuesta no depende del orden en que exploren: si la cadena se acepta,
cualquier búsqueda encuentra la aceptación antes de pasar del límite, y si no se acepta, lo que cuenta es
cuántas configuraciones hay, y eso no depende del orden.

## Límites

- $1 \leq |Q| \leq 200$, $1 \leq |\Sigma| \leq 30$ y $0 \leq |\Gamma| \leq 30$. A lo sumo 2000 transiciones.
- El nombre de un estado tiene entre 1 y 20 caracteres visibles, sin espacios. No empieza con `#`, no termina
  con `:` y no es `eps`. Un nombre puede ser prefijo de otro (`q1` y `q10`), y puede ser igual a un símbolo (un
  estado `0`, un estado `$`).
- Un símbolo, de la entrada o de la pila, es un solo carácter visible distinto de `#`. Un mismo carácter puede
  estar en los dos alfabetos.
- $1 \leq k \leq 100$, y cada cadena tiene a lo sumo 200 símbolos, todos del alfabeto de entrada.
- La entrada siempre describe un PDA válido: no tienen que detectar errores en la descripción.

## Ejemplo

Para la entrada de arriba, la salida es:

```text
acepta
acepta
rechaza
rechaza
```

Con `0011` el autómata marca el fondo de la pila con `$`, guarda los dos ceros, los saca con los dos unos y,
al ver otra vez `$`, pasa a `q3`. La segunda cadena es la vacía: el estado inicial `q0` es de aceptación, y
no hace falta moverse. Con `001` sobra un cero en la pila y `q2` no puede pasar a `q3`. Con `10` no hay ningún
cero que sacar cuando llega el `1`.

Un ejemplo con las tres respuestas. Es el autómata del caso `casos/10.in`, con tres de sus cadenas: el de
arriba, ahora con `q3` como único estado de aceptación y con un estado `loco` al que se llega leyendo una `c`.

```text
states: q0 q1 q2 q3 loco
alphabet: 0 1 c
stack: 0 $ x
start: q0
accept: 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
q1 c eps -> loco eps
q2 c eps -> loco eps
loco eps eps -> loco x
strings: 3
0011
0c
001
```

```text
acepta
limite
rechaza
```

Con `0c` el autómata llega a `loco`, que pone una `x` tras otra: hay una configuración distinta por cada altura
de la pila, y ninguna es de aceptación. Con `0011` y con `001` nunca se lee una `c`, así que `loco` no se
alcanza y las configuraciones son pocas.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

Hay dos maneras de hacerlo mal, y los casos traen las dos.

**Sin recordar las configuraciones vistas, la búsqueda puede no terminar.** Un ciclo de transiciones `eps` que
no cambia la pila, como `p eps eps -> q eps` junto con `q eps eps -> p eps`, vuelve a la misma configuración.
Los casos 06 y 07 tienen ciclos así.

**Recordar solo el camino actual no alcanza.** Una búsqueda en profundidad que evita repetir configuraciones
dentro del camino que está siguiendo sí termina, pero vuelve a explorar una configuración cada vez que llega a
ella por un camino distinto. En el caso 15, cada `a` se puede leer de tres maneras y muchas de ellas terminan
en la misma configuración: para `a^30` hay $3^{30}$ caminos y menos de 4000 configuraciones. En el caso 16 son
$2^{100}$ caminos y unas 700 configuraciones. Con un conjunto de configuraciones vistas, compartido por toda
la búsqueda de una cadena, cada configuración se explora una sola vez, y el juez deja de dar `TLE`. Además, sin
ese conjunto no hay cómo contar las configuraciones distintas, que es lo que pide el límite.

Con los límites de arriba alcanza la representación directa: una configuración con una copia de su pila en un
`std::string`, y las vistas en un `std::set`. En el peor caso son 10 001 configuraciones por cadena, con pilas
de hasta 10 001 símbolos.

## Qué se practica aquí

En `code/week-06/pda.h` hay un `struct Pda` y una función `simulate` que hace esta búsqueda: es lo que usan los
ejemplos de los apuntes, y pueden leerla cuanto quieran. `solution.cpp` se escribe **sin incluir `pda.h`**: el
juez compila ese único archivo, y el lector de `pda.h` no entiende el bloque `strings:`. El trabajo está en
tres cosas.

- **Qué es una configuración y cuándo dos son la misma.** Estado, posición y pila completa. Dos caminos que
  llegan al mismo estado y a la misma posición con pilas distintas no se pueden juntar.
- **Qué transiciones se pueden usar** desde una configuración: las cuatro combinaciones de leer o no leer y de
  sacar o no sacar. Con la entrada terminada solo quedan las que leen `eps`, y con la pila vacía las que sacan
  `eps`.
- **Cuándo detenerse**: al aceptar, al quedarse sin configuraciones o al pasar del límite.

Los casos traen, entre otros: la cadena vacía, un PDA sin estados de aceptación, uno sin transiciones y sin
símbolos de pila, uno que acepta con la pila sin vaciar, uno sin marca de fondo que intenta sacar de la pila
vacía, estados inalcanzables, nombres iguales a los símbolos, ciclos de transiciones `eps` de los dos tipos, y
dos autómatas casi iguales que con la misma cadena tienen exactamente 10 000 y 10 001 configuraciones.

## Cómo avanzar

```sh
make        # compila solution.cpp en build/
make test   # corre el juez con todos los casos
```

1. Lean la descripción y las cadenas. Empiecen con `casos/01.in`. Lean por líneas, con `std::getline`: una
   línea vacía es la cadena $\varepsilon$, y `>>` se la salta.
2. Representen el autómata con los seis componentes de la definición, con los mismos nombres: `states`,
   `alphabet`, `stack`, `delta`, `start` y `accept`. El esqueleto trae un `struct Pda` y un `struct Config` con
   una propuesta de tipos.
3. Escriban la búsqueda con el conjunto de configuraciones vistas. Por niveles o en profundidad: la respuesta
   es la misma. Pasen primero los casos 01 a 09, que no llegan al límite.
4. Agreguen el límite y pasen los casos 10 a 14. Antes de correr el juez, respondan a mano con el caso 12: si
   con cada `a` el autómata pone un `0` o un `1`, ¿cuántas configuraciones alcanzables hay después de 12
   símbolos? ¿Y después de 13?
5. Escriban ustedes, en el mismo formato, el PDA de los palíndromos de longitud par sobre
   $\{\mathtt{a}, \mathtt{b}\}$, y pruébenlo con su simulador:

   ```sh
   { cat palindromos.pda; printf 'strings: 4\nabba\n\naba\nabab\n'; } | build/solution
   ```

   Debe imprimir `acepta`, `acepta`, `rechaza`, `rechaza`. Después prueben los autómatas de la clase, que
   están en `../../machines/`: a un archivo `.pda` le falta solo el bloque de cadenas.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

## Para seguir

Opcional, sin casos en el juez.

- Cambien el PDA de los palíndromos para que acepte también los de longitud impar. ¿Cuántas transiciones
  agregaron?
- Con `build/cfg_to_pda` de la carpeta de la semana, conviertan la gramática `../../machines/expr.cfg` en un
  PDA y denle a su simulador las cadenas `a+a*a` y `a+`. ¿Por qué la segunda responde `limite` y no `rechaza`?
  ¿Qué regla de la gramática produce el ciclo que hace crecer la pila?
- Cuando acepta, hagan que su programa imprima además una ejecución de aceptación: la secuencia de
  configuraciones desde la inicial. Hace falta guardar, para cada configuración, desde cuál se llegó a ella.
- Las pilas de dos configuraciones vecinas se diferencian solo en la cima. En lugar de copiar la pila en cada
  configuración, guarden cada pila distinta una sola vez, como un par (símbolo de la cima, pila de debajo), y
  que la configuración lleve solo su número. ¿Cuánta memoria usa ahora el caso 11?
