# ¿Son equivalentes dos DFA?

Dos autómatas finitos deterministas (DFA) pueden verse muy distintos y reconocer el mismo lenguaje: uno tiene
estados de más, el otro salió de una construcción automática y nadie lo dibujó. En la clase se demostró que
decidir si $L(A) = L(B)$ es posible: el lenguaje $\mathrm{EQ}_{\mathrm{DFA}}$ es decidible. Este laboratorio
convierte esa demostración en un programa que además, cuando los autómatas no son equivalentes, lo prueba con
una cadena: una de las más cortas que uno acepta y el otro rechaza.

## Entrada

Dos descripciones de DFA en el formato `.dfa` de [`code/formats.md`](../../../formats.md), separadas por una
línea que contiene solo `---`. El primero es $A$ y el segundo es $B$.

```text
# A: cadenas binarias que terminan en 01.
states: q0 q1 q2
alphabet: 0 1
start: q0
accept: q2
delta:
q0 0 q1
q0 1 q0
q1 0 q1
q1 1 q2
q2 0 q1
q2 1 q0
---
# B: un intento equivocado. Desde q2, con 0, vuelve a q0.
states: q0 q1 q2
alphabet: 0 1
start: q0
accept: q2
delta:
q0 0 q1
q0 1 q0
q1 0 q1
q1 1 q2
q2 0 q0
q2 1 q0
```

- La primera descripción termina en la línea `---`, y la segunda donde termina la entrada.
- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea, también entre
  las transiciones y justo después de `---`.
- Puede haber líneas vacías antes de `delta:`. Después de `delta:` no hay líneas vacías.
- En cada descripción, `states:`, `alphabet:`, `start:`, `accept:` y `delta:` vienen en ese orden, y `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.
- **Los dos autómatas tienen los mismos símbolos**, pero `alphabet:` puede listarlos en otro orden.
- **Los nombres de los estados son de cada autómata.** Que los dos tengan un estado `q0` no significa nada:
  son estados distintos.

## Salida

Si $L(A) = L(B)$, una línea:

```text
equivalentes
```

Si no, dos líneas: `distintos` y una cadena $w$ de **longitud mínima** entre las que están en exactamente uno
de los dos lenguajes.

```text
distintos
0101
```

La cadena vacía no se puede imprimir como una línea vacía, porque el juez no la vería. Si la cadena más corta
que separa a los autómatas es $\varepsilon$, se imprime `eps`, como en el resto de los formatos del curso:

```text
distintos
eps
```

Suele haber varias cadenas de longitud mínima, y cualquiera vale. El juez usa un verificador: comprueba que
su cadena solo usa símbolos del alfabeto, que uno de los autómatas la acepta y el otro no, y que tiene la
misma longitud que la respuesta de referencia. No compara el texto.

## Límites

- $1 \leq |Q_A|, |Q_B| \leq 50\,000$ y $1 \leq |\Sigma| \leq 14$. Cada autómata tiene a lo sumo 200 000
  transiciones.
- Un símbolo es un dígito o una letra de la `a` a la `d`. Así, `eps` nunca se confunde con una cadena de
  tres símbolos.
- El nombre de un estado tiene entre 1 y 30 caracteres visibles, sin espacios. No empieza con `#` ni con `-`,
  y no termina con `:`. Puede llevar llaves, comas y paréntesis, como `{q0,q1}`.
- **A lo sumo 200 000 pares $(p, q)$ son alcanzables** desde el par de estados iniciales, donde $p$ es un
  estado de $A$ y $q$ uno de $B$. El número total de pares, $|Q_A| \cdot |Q_B|$, puede llegar a
  2 500 000 000.
- La entrada siempre describe dos DFA válidos: no tienen que detectar errores.

## Ejemplo

Para la entrada de arriba la salida es `distintos` y `0101`. Con esa cadena, $A$ pasa por $q_0, q_1, q_2, q_1,
q_2$ y acepta. $B$ pasa por $q_0, q_1, q_2, q_0, q_0$ y rechaza: al volver a $q_0$ olvidó el $\mathtt{0}$ que
acababa de leer. Ninguna cadena de longitud 3 o menos los separa.

## Tiempo

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

## La idea

La demostración de la clase construye un tercer autómata $C$, con la construcción del producto: sus estados
son los pares $(p, q)$, y un par es de aceptación cuando exactamente uno de los dos estados lo es. Entonces
$C$ acepta justo las cadenas en las que $A$ y $B$ no coinciden, y $A$ y $B$ son equivalentes si y solo si
$L(C) = \emptyset$, cosa que se decide viendo si algún estado de aceptación de $C$ es alcanzable.

Como demostración está completa. Como programa tiene un problema: $C$ tiene $|Q_A| \cdot |Q_B|$ estados, y
casi siempre se llega a muy pocos. En el caso 16 los dos autómatas tienen 50 000 estados: el producto tendría
2 500 000 000 de pares, y desde el inicial se alcanzan 50 000. Construirlo entero no entra ni en el tiempo ni
en la memoria. Lo que hay que hacer es no construirlo:

1. Empezar en el par $(q_A, q_B)$ de los estados iniciales.
2. Buscar **en anchura**. De cada par $(p, q)$ que sale de la cola, y con cada símbolo $a$, se calcula el par
   $(\delta_A(p, a), \delta_B(q, a))$; si es nuevo, entra a la cola.
3. Si sale de la cola un par en el que un estado es de aceptación y el otro no, la respuesta es `distintos`.
   La cadena se reconstruye hacia atrás, guardando de cada par desde cuál se llegó y con qué símbolo.
4. Si la cola se vacía, la respuesta es `equivalentes`.

La búsqueda en anchura descubre los pares por distancia creciente desde el inicial, y la distancia de un par
es la longitud de la cadena más corta que lleva a él. Por eso el primer par "malo" que aparece da una cadena
de longitud mínima. Una búsqueda en profundidad también decide si son equivalentes, pero la cadena que
entrega puede ser mucho más larga, y el verificador la rechaza.

Otra idea que no sirve: probar todas las cadenas, de las más cortas a las más largas. Es correcta, porque si
los autómatas son distintos alguna cadena de longitud menor que $|Q_A| \cdot |Q_B|$ los separa, y entonces se
puede parar ahí. Pero con dos símbolos hay $2^n$ cadenas de longitud $n$: en el caso 02, con autómatas de 3 y
7 estados que sí son equivalentes, habría que probar todas las de longitud hasta 20 antes de responder.

## Cómo avanzar

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

Los dos casos más grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.
`solution.cpp` se escribe sin incluir los archivos de la carpeta de la semana: el juez compila ese único
archivo.

1. Lean los dos autómatas. Empiecen con `casos/01.in`. Lean por líneas, con `std::getline`, y fíjense en qué
   línea termina cada descripción. Guarden cada estado por su posición en la lista, y pasen los nombres a
   posiciones una sola vez, al leer: con 50 000 estados, buscar un nombre en una lista por cada transición es
   demasiado lento.
2. Respondan `equivalentes` o `distintos` con la búsqueda en anchura sobre los pares. Un par $(p, q)$ se
   puede guardar como el número $p \cdot |Q_B| + q$, que no entra en un `int`: usen `long long`. Para saber
   si un par ya se visitó sirve un `std::unordered_set` o un `std::set` de esos números. Un arreglo con una
   casilla por cada par posible es justo el producto completo que hay que evitar.
3. Agreguen la cadena. Antes de correr el juez, respondan a mano: ¿qué imprime su programa si un autómata
   acepta $\varepsilon$ y el otro no? ¿Y si los dos tienen `accept:` vacío?
4. Pasen los casos grandes, del 13 al 17. Si alguno da `TLE`, cuenten cuántos pares genera su programa y
   compárenlo con los 200 000 del enunciado.
5. Comprueben con su programa los autómatas de `machines/`, que reconocen todos "el sexto símbolo desde el
   final es $\mathtt{1}$":

   | Archivo | Qué es | Estados |
   |---|---|---|
   | `kth6.nfa` | El NFA de la semana 2 | 7 |
   | `kth6_subsets.dfa` | Su construcción de subconjuntos, solo con los subconjuntos alcanzables | 64 |
   | `kth6_all.dfa` | La construcción de subconjuntos con todos los subconjuntos | 128 |
   | `kth6_history.dfa` | Un DFA que recuerda los últimos símbolos leídos, con un estado por cada cadena de longitud a lo sumo 6 | 127 |
   | `kth6_min.dfa` | El DFA mínimo, como lo deja la minimización de la semana 4 | 64 |
   | `kth6_wrong.dfa` | El mínimo con dos estados fusionados por error | 63 |

   Para comparar dos archivos se arma la entrada con la línea `---` en medio:

   ```sh
   { cat machines/kth6_subsets.dfa; echo '---'; cat machines/kth6_min.dfa; } | build/solution
   ```

   Debe imprimir `equivalentes`. Comparen también `kth6_all.dfa` con `kth6_history.dfa`, y el DFA que su
   propio programa de la semana 2 produjo para $k = 6$ con el que dejó su minimizador de la semana 4. Después
   comparen `kth6_min.dfa` con `kth6_wrong.dfa`: ¿qué cadena imprime su programa, y por qué tiene 7 símbolos y
   no menos?

Los seis archivos los escribe el programa `make_kth` de la carpeta de la semana (`make kth`): arma el NFA,
le aplica la construcción de subconjuntos de las dos maneras, escribe el autómata que recuerda los últimos
símbolos, lo minimiza, y en el mínimo fusiona el estado al que se llega con `11` con el estado al que se
llega con `10`.

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

## Los casos

| Casos | Qué prueban |
|---|---|
| 01 a 03 | Los ejemplos de los apuntes: distintos con una cadena de 4 símbolos, equivalentes con 3 y 7 estados, y distintos con $\varepsilon$ |
| 04 a 06 | El lenguaje vacío de dos maneras (sin estados de aceptación, y con uno inalcanzable), el vacío contra uno que no lo es, y $\Sigma^*$ con un estado inalcanzable |
| 07 | Los mismos nombres en los dos autómatas, el alfabeto en otro orden, comentarios y transiciones desordenadas |
| 08 y 09 | Un solo símbolo: ciclos de 7 y 11 estados, en los que se alcanzan los 77 pares, y ciclos de 91 y 7 |
| 10 y 11 | Los autómatas de `machines/` |
| 12 | 14 símbolos y 200 estados |
| 13 | 2000 estados cada uno: el producto completo tiene 4 000 000 de pares y se alcanzan 2000 |
| 14 y 15 | 194 686 pares alcanzables; en el 15, muchas cadenas de longitud mínima |
| 16 | 50 000 estados cada uno, equivalentes |
| 17 | 40 000 y 50 000 estados; la cadena más corta que los separa tiene 39 999 símbolos |

## Para seguir

Opcional, sin casos en el juez.

- Con este programa y el complemento se decide también si $L(A) \subseteq L(B)$. ¿Qué pares hay que buscar?
- Cuenten los pares que visita su programa en el caso 14 y expliquen el número: ¿por qué son exactamente
  $311 \cdot 313 \cdot 2$?
- Hay un algoritmo que decide la equivalencia sin cola ni distancias, uniendo en una misma clase los estados
  que tendrían que ser equivalentes (Hopcroft y Karp, con la estructura de conjuntos disjuntos de
  Algoritmos). Es casi lineal, pero la cadena que encuentra no es de las más cortas. ¿Por qué?
