# Un simulador de DFA

El primer programa del curso es el que van a usar todo el semestre para probar sus autómatas: recibe la
descripción de un autómata finito determinista (DFA) y una lista de cadenas, y dice por cada cadena si el
autómata la acepta.

Un DFA es $M = (Q, \Sigma, \delta, q_0, F)$. Acepta una cadena $w$ si, empezando en $q_0$ y siguiendo $\delta$
con cada símbolo de $w$, de izquierda a derecha, termina en un estado de $F$.

## Entrada

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

```text
# Cadenas binarias con una cantidad par de unos.
states: par impar
alphabet: 0 1
start: par
accept: par
delta:
par 0 par
par 1 impar
impar 0 impar
impar 1 par
strings: 3
0110

111
```

- 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:`, `start:`, `accept:` y `delta:` vienen siempre en ese orden. `accept:` puede no
  tener ningún estado.
- Después de `delta:` hay exactamente una línea `estado símbolo destino` por cada par de estado y símbolo, en
  cualquier orden.
- `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: `acepta` si el autómata la acepta y `rechaza` si no.

## Límites

- $1 \leq |Q| \leq 2000$ y $1 \leq |\Sigma| \leq 26$.
- El nombre de un estado tiene entre 1 y 20 caracteres visibles, sin espacios. No empieza con `#` ni termina
  con `:`. Un nombre puede ser prefijo de otro (`q1` y `q10`), y puede ser igual a un símbolo (un estado `0` y
  un símbolo `0`).
- Un símbolo es un solo carácter visible, distinto de `#`.
- $1 \leq k \leq 100\,000$. Las longitudes de las cadenas suman a lo sumo 1 000 000.
- Todas las cadenas están formadas solo por símbolos del alfabeto.
- La entrada siempre describe un DFA válido: no tienen que detectar errores en la descripción.

## Ejemplo

Para la entrada de arriba, la salida es:

```text
acepta
acepta
rechaza
```

`0110` tiene dos unos. La segunda cadena es la vacía, que tiene cero unos, y cero es par. `111` tiene tres.

## Tiempo

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

Con los límites de arriba, $\delta$ puede tener 52 000 transiciones y hay que seguir hasta 1 000 000 de símbolos.
Si por cada símbolo recorren la lista de transiciones hasta encontrar la que toca, son demasiadas
comparaciones y el juez da `TLE`. Guarden $\delta$ de modo que seguir una transición no dependa de cuántas hay: una
tabla indexada por el número del estado y el del símbolo, o un `std::map`.

## Qué se practica aquí

En `code/week-01/dfa.h` ya hay un `struct Dfa` y una función que lee un archivo `.dfa` y lo ejecuta: es lo
que usan los ejemplos de los apuntes, y pueden leerlo cuanto quieran. Simular un DFA son tres líneas, y no es
lo difícil de este laboratorio. El trabajo está en **leer el formato sin tropezar** y en **los casos de
borde**, y por eso `solution.cpp` se escribe **sin incluir `dfa.h`**: el juez compila ese único archivo, y el
lector de `dfa.h` no entiende el bloque `strings:`.

Los casos traen, entre otros: la cadena vacía (también como última línea de la entrada), un DFA sin estados
de aceptación, uno que acepta todo, estados inalcanzables, comentarios entre las transiciones, transiciones
desordenadas, nombres que son prefijo de otros y nombres iguales a los símbolos.

## Cómo avanzar

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

Los tres casos grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.

1. Lean la descripción y las cadenas, y respondan por cada una. Empiecen con `casos/01.in`. Lean por líneas,
   con `std::getline`: `>>` se salta las líneas vacías, y aquí una línea vacía es una cadena.
2. Representen el autómata con los cinco componentes de la definición, con los mismos nombres: `states`,
   `alphabet`, `delta`, `start` y `accept`. El esqueleto trae un `struct Dfa` con una propuesta de tipos.
3. Pasen los casos de borde. Antes de correr el juez, respondan a mano: ¿qué responde un DFA sin estados de
   aceptación con la cadena vacía? ¿Y uno con un solo estado, que es de aceptación?
4. Prueben con su simulador los DFA de la clase, que están en `../../machines/`. A un archivo `.dfa` le falta
   solo el bloque de cadenas:

   ```sh
   { cat ../../machines/ends_01.dfa; printf 'strings: 3\n01\n\n110\n'; } | build/solution
   ```

   Debe imprimir `acepta`, `rechaza`, `rechaza`. Después escriban ustedes, en el mismo formato, un DFA de los
   ejercicios de los apuntes (por ejemplo, las cadenas sobre $\{\mathtt{a}, \mathtt{b}\}$ que no contienen `aa`) y pruébenlo con
   cadenas que hayan resuelto antes a mano.

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

## Para seguir

Opcional, sin casos en el juez. Escriban un segundo programa que lea **dos** DFA con el mismo alfabeto, uno
después del otro, y escriba en formato `.dfa` el autómata de la construcción del producto que reconoce la
**intersección** de sus lenguajes: sus estados son los pares $(p, q)$, y con cada símbolo avanza en los dos a
la vez.

- El nombre de un estado no puede llevar espacios: `(par,q0)` sirve.
- Para comprobarlo, pásenle la salida a su simulador con algunas cadenas y comparen con lo que responden los
  dos autómatas por separado. El caso `casos/10.in` es un producto escrito así.
- ¿Cuántos estados tiene el resultado si los autómatas tienen 3 y 4 estados? Agreguen una opción para
  escribir solo los estados a los que se llega desde el inicial, y cuenten otra vez.
- Cambien solo los estados de aceptación para obtener la **unión**.
