# Minimizar un DFA

Ejercicio opcional de la semana 4: la sesión de laboratorio de esta semana es para la Práctica 1.

Dos autómatas finitos deterministas (DFA) pueden reconocer el mismo lenguaje con distinta cantidad de estados.
Entre todos los que reconocen un lenguaje hay uno con el menor número posible, el **DFA mínimo**, y es único
salvo los nombres de sus estados. Su programa recibe un DFA y escribe el DFA mínimo que reconoce el mismo
lenguaje.

El algoritmo está en los apuntes de la semana 4, sección *Minimizar un DFA*: quitar los estados inalcanzables,
partir de la partición $\{F, Q - F\}$ y refinarla hasta que no cambie.

## Entrada

La descripción de un DFA en el formato `.dfa` de [`code/formats.md`](../../../formats.md):

```text
$ cat casos/01.in
# Cadenas binarias que contienen 1001, escrito con descuido: 8 estados para un lenguaje
# que necesita 5.
# q0: todavía no se leyó nada.            q4: no hay avance, y ya se leyó algo.
# q1: lo leído termina en 1.              q2: termina en 10.       q3: termina en 100.
# q5, q6: ya apareció 1001 (q5 si lo último fue 1, q6 si fue 0).
# q7: quedó de una versión anterior. Ninguna transición llega a él.
states: q0 q1 q2 q3 q4 q5 q6 q7
alphabet: 0 1
start: q0
accept: q5 q6 q7
delta:
q0 0 q4
q0 1 q1
q1 0 q2
q1 1 q1
q2 0 q3
q2 1 q1
q3 0 q4
q3 1 q5
q4 0 q4
q4 1 q1
q5 0 q6
q5 1 q5
q6 0 q6
q6 1 q5
q7 0 q3
q7 1 q7
```

- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea, también entre
  las transiciones.
- Puede haber líneas vacías antes de `delta:`. Después de `delta:` 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.
- No hay bloque `strings:`. La entrada termina con la última transición.

## Salida

Un DFA en el mismo formato, que reconozca el mismo lenguaje que el de la entrada y tenga el menor número
posible de estados.

- El alfabeto es el de la entrada. Sus símbolos pueden ir en cualquier orden.
- Los estados pueden llamarse como quieran y escribirse en cualquier orden. Un nombre tiene entre 1 y 20
  caracteres visibles, sin espacios, no empieza con `#` y no termina con `:`. Lo más simple es numerarlos. No
  armen el nombre de un bloque pegando los nombres de sus estados: puede pasar de 20 caracteres.
- La función de transición es total: una línea por cada par de estado y símbolo, sin repetir.
- Pueden escribir comentarios.

Para la entrada de arriba, esta es una salida correcta:

```text
$ cat casos/01.out
states: m0 m1 m2 m3 m4
alphabet: 0 1
start: m0
accept: m4
delta:
m0 0 m0
m0 1 m1
m1 0 m2
m1 1 m1
m2 0 m3
m2 1 m1
m3 0 m0
m3 1 m4
m4 0 m4
m4 1 m4
```

No es la única. Otra salida con cinco estados que reconozca el mismo lenguaje también es correcta, se llamen
como se llamen.

## Límites

- $1 \leq |Q| \leq 2000$ y $1 \leq |\Sigma| \leq 26$.
- El nombre de un estado de la entrada 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 `#`.
- La entrada siempre describe un DFA válido: no tienen que detectar errores en la descripción.

## El verificador

Como hay muchas respuestas correctas, el juez no compara su salida con `casos/NN.out`. Usa
`verificador.cpp`, que pueden leer, y que comprueba tres cosas:

1. La salida es un DFA bien formado y completo, con el alfabeto de la entrada.
2. Tiene tantos estados como el DFA de `casos/NN.out`, que es el mínimo.
3. Reconoce el mismo lenguaje que el DFA de la entrada. Para eso recorre los pares de estados a los que se
   llega leyendo la misma cadena en los dos autómatas, y busca un par en el que uno acepte y el otro no.

Por el teorema de unicidad de los apuntes, un DFA equivalente con el número mínimo de estados es el DFA
mínimo, así que con eso basta. Cuando la salida es incorrecta, el juez muestra el motivo al lado del veredicto
`WA`: qué línea está mal formada, cuántos estados tiene la salida y cuántos el mínimo, o una cadena, de las más
cortas, en la que la salida y la entrada no coinciden.

## Tiempo

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

Los cuatro casos grandes tienen 2000 estados. Hay unos dos millones de pares de estados, y decidir cada par por
separado, buscando un sufijo que lo distinga, es demasiado: una solución así pasa los diez casos pequeños y da
`TLE` en los cuatro grandes. El refinamiento decide todos los pares a la vez: en cada ronda calcula una firma
por estado, y agrupa.

Dos de los casos grandes necesitan cerca de mil y cerca de dos mil rondas. Para que cada ronda sea rápida,
numeren los estados y los símbolos al leer la entrada, y guarden $\delta$ y la partición en vectores de
enteros. Agrupar las firmas con un `std::map<std::vector<int>, int>` alcanza.

## Qué se practica aquí

En `code/week-04/minimize.h` hay una minimización que pueden leer: es la de los apuntes, escrita para que se
parezca a las definiciones, con los nombres de los estados como cadenas, y no para autómatas grandes.
`solution.cpp` se escribe sin incluir los encabezados de la semana: el juez compila ese único archivo.

Los casos traen, entre otros: estados inalcanzables, algunos de ellos de aceptación; un autómata sin estados de
aceptación y uno con todos de aceptación, cuyo mínimo tiene un solo estado; uno que ya es mínimo; un estado
inicial que se fusiona con otros; comentarios entre las transiciones 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 cuatro casos grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.

1. Lean el DFA y escríbanlo de nuevo tal cual, con sus propios nombres para los estados. Con eso ya pasa
   `casos/02.in`, que es mínimo, y saben que leen y escriben bien el formato.
2. Eliminen los estados inalcanzables, con un recorrido desde el estado inicial. Antes de correr el juez,
   respondan a mano: ¿cuántos estados tiene el mínimo de un DFA sin estados de aceptación? ¿Y el de `casos/05.in`,
   que tiene estados de aceptación pero todos inalcanzables?
3. Refinen la partición $\{F, Q - F\}$ hasta que una ronda no cambie el número de bloques, y escriban un
   estado por bloque. Para depurar, comparen sus particiones con las que imprime el programa de la clase:

   ```sh
   ../../build/minimize casos/01.in
   ```

4. Corran `make test`. Si un caso da `WA`, el mensaje del verificador dice por dónde empezar: si sobran
   estados, alguna ronda dejó juntos a dos que debía separar o quedaron inalcanzables; si aparece una cadena,
   síganla a mano en la entrada y en su salida.

## El autómata de k = 6

En el laboratorio de la semana 2 midieron cuántos estados da la construcción de subconjuntos para "el
$k$-ésimo símbolo desde el final es $\mathtt{1}$". Para $k = 6$, el NFA tiene 7 estados y el DFA debió salirles
con 64. Pasen ese DFA por su programa de esta semana y cuenten los estados del resultado. Si no lo tienen a la
mano, el programa `kth_from_end` de `code/week-04` escribe uno igual salvo los nombres: lo construye
directamente, con un estado por cada combinación de los últimos 6 símbolos. El mismo autómata es `casos/09.in`.

```sh
../../build/kth_from_end 6 > k6.dfa
build/solution < k6.dfa | head -1 | wc -w    # los estados, más la palabra states:
```

Con la minimización de la clase, el resultado es este:

```text
$ ../../build/kth_from_end 6 | ../../build/minimize - | grep -E '^(estados|P[0-9]|DFA)'
estados: 64, alcanzables: 64. No hay nada que quitar
P0: 2 bloques
P1: 4 bloques
P2: 8 bloques
P3: 16 bloques
P4: 32 bloques
P5: 64 bloques
P6 = P5: la partición ya no cambia
DFA mínimo: 64 estados
```

Entran 64 estados y salen 64: no se fusiona ninguno. La construcción de subconjuntos no desperdició nada, y es
lo que dice el teorema de los apuntes: todo DFA de ese lenguaje tiene al menos $2^6 = 64$ estados, porque las
64 cadenas de longitud 6 son distinguibles dos a dos. Las 5 rondas que cambian algo corresponden a los
sufijos $\mathtt{0}, \mathtt{00}, \ldots, \mathtt{00000}$ de esa demostración.

Comparen con un autómata que sí tenía estados de más, el de `casos/07.in`:

```text
$ ../../build/minimize casos/07.in | grep -E '^(estados|P[0-9]|DFA)'
estados: 7, alcanzables: 7. No hay nada que quitar
P0: 2 bloques
P1: 3 bloques
P2 = P1: la partición ya no cambia
DFA mínimo: 3 estados
```

## Para seguir

Opcional, sin casos en el juez.

- Escriban un segundo programa que lea **dos** DFA con el mismo alfabeto y diga si reconocen el mismo
  lenguaje: minimicen los dos y comprueben si son iguales salvo los nombres, recorriéndolos a la vez desde los
  estados iniciales. Les servirá en el laboratorio de la semana 9.
- Midan cuántas rondas hace su programa en cada caso grande. ¿Por qué el caso 12, con 2000 estados al azar,
  necesita tan pocas, y el caso 14 tantas?
