# De NFA a DFA

En clase se demostró que todo autómata finito no determinista (NFA) tiene un autómata finito determinista (DFA)
equivalente, con la construcción de subconjuntos. Aquí la programan: su programa recibe un NFA, que puede tener
transiciones $\varepsilon$, y escribe un DFA que reconoce el mismo lenguaje.

Si el NFA es $N = (Q, \Sigma, \delta, q_0, F)$ y $E(S)$ es la clausura $\varepsilon$ de un conjunto de estados
$S$, el DFA de la construcción tiene un estado por cada conjunto de estados de $N$:

- su estado inicial es $E(\{q_0\})$;
- desde el conjunto $S$, con el símbolo $a$, va al conjunto $E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)$;
- un conjunto es de aceptación si contiene algún estado de $F$.

## Entrada

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

```text
# Cadenas binarias que contienen 101 o 11.
states: q0 q1 q2 q3
alphabet: 0 1
start: q0
accept: q3
delta:
q0 0 q0
q0 1 q0 q1
q1 0 q2
q1 eps q2
q2 1 q3
q3 0 q3
q3 1 q3
```

- 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, y la descripción
  termina donde termina la entrada.
- `states:`, `alphabet:`, `start:`, `accept:` y `delta:` vienen siempre en ese orden. `accept:` puede no tener
  ningún estado.
- Después de `delta:`, cada línea es `estado símbolo destino…`, con uno o más destinos. Una transición
  $\varepsilon$ lleva `eps` en el lugar del símbolo.
- Un par de estado y símbolo que no aparece no tiene transiciones. Puede no haber ninguna línea después de
  `delta:`.
- El mismo par puede aparecer en varias líneas, y un destino puede estar repetido: los destinos de todas esas
  líneas se juntan en un solo conjunto.

## Salida

Un DFA equivalente al NFA de la entrada, en el formato `.dfa` del mismo documento: los cinco campos en su orden
y, después de `delta:`, exactamente una línea `estado símbolo destino` por cada par de estado y símbolo.

- El alfabeto del DFA tiene los mismos símbolos que el del NFA, en cualquier orden.
- Los nombres de los estados los eligen ustedes. Cada uno tiene entre 1 y 20 caracteres visibles, sin espacios,
  no empieza con `#` y no termina con `:`.
- El DFA tiene **a lo sumo 10 000 estados**.

Hay muchas respuestas correctas: los estados pueden llamarse de otro modo, ir en otro orden o ser más o menos
que los de `casos/NN.out`. El juez no compara textos. Usa un verificador, que se describe más abajo.

## Límites

- $1 \leq |Q| \leq 60$ y $1 \leq |\Sigma| \leq 10$.
- 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, puede ser igual a un símbolo, y puede ser `eps`: en una línea de
  `delta:`, lo que decide qué es cada palabra es su posición.
- Un símbolo es un solo carácter visible, distinto de `#`.
- Se garantiza que la construcción de subconjuntos, **si solo genera los subconjuntos alcanzables** desde
  $E(\{q_0\})$, produce a lo sumo 5000 estados.
- La entrada siempre describe un NFA válido: no tienen que detectar errores en la descripción.

## Ejemplo

Para la entrada de arriba, una salida correcta es:

```text
states: s0 s1 s2 s3 s4 s5
alphabet: 0 1
start: s0
accept: s3 s4 s5
delta:
s0 0 s0
s0 1 s1
s1 0 s2
s1 1 s3
s2 0 s0
s2 1 s3
s3 0 s4
s3 1 s3
s4 0 s5
s4 1 s3
s5 0 s5
s5 1 s3
```

Es la de `casos/02.out`. Los seis estados son los subconjuntos alcanzables, numerados en el orden en que una
cola los encuentra:

| Nombre | Subconjunto |
|---|---|
| `s0` | $\{q_0\}$ |
| `s1` | $\{q_0, q_1, q_2\}$ |
| `s2` | $\{q_0, q_2\}$ |
| `s3` | $\{q_0, q_1, q_2, q_3\}$ |
| `s4` | $\{q_0, q_2, q_3\}$ |
| `s5` | $\{q_0, q_3\}$ |

Desde $\{q_0\}$ con $\mathtt{1}$ se llega a $q_0$ y a $q_1$, y la clausura $\varepsilon$ agrega $q_2$: por eso
`s0 1 s1`. El NFA tiene 4 estados y $2^4 = 16$ subconjuntos, pero desde el inicial solo se alcanzan estos 6.

## Tiempo

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

Un NFA de 60 estados tiene $2^{60}$ subconjuntos, más de $10^{18}$. Un programa que escribe un estado por cada
subconjunto no termina nunca con ese caso, y el juez da `TLE`. Con 18 estados sí termina, pero escribe $2^{18} =
262\,144$ estados y el verificador lo rechaza por pasarse de 10 000. La construcción tiene que partir de
$E(\{q_0\})$ y generar solo los subconjuntos que va encontrando.

## El verificador

`make test` compila `verificador.cpp` y el juez lo llama con cada caso. Pueden leerlo: son las ideas de la semana
1. Con la salida de su programa hace tres cosas.

1. **Comprueba que es un DFA bien formado**: los cinco campos, ningún estado repetido, el estado inicial y los
   de aceptación dentro de `states:`, y exactamente una transición por cada par de estado y símbolo.
2. **Comprueba los límites**: el mismo alfabeto que el NFA, a lo sumo 10 000 estados, nombres de hasta 20
   caracteres.
3. **Compara los lenguajes.** Recorre a la vez el NFA, con su conjunto de estados activos, y el DFA que
   ustedes entregaron, como en la construcción del producto: parte del par formado por $E(\{q_0\})$ y su estado
   inicial, y avanza en los dos con cada símbolo. Si llega a un par en el que uno acepta y el otro no, las
   máquinas no son equivalentes, y la cadena que llevó hasta ese par lo demuestra.

Cuando algo falla, el juez muestra el motivo al lado del veredicto. Con una solución que olvida la clausura
$\varepsilon$ del estado inicial, el caso 07 da:

```text
07           WA     0.01 s  no reconocen el mismo lenguaje: la cadena vacía la acepta el NFA y la rechaza el DFA
```

La cadena que muestra es de las más cortas en las que las dos máquinas difieren: síganla a mano en el NFA y en
su DFA.

## Qué se practica aquí

En `code/week-02/nfa.h` hay un `struct Nfa` y una función `subset_construction`: es lo que usan los ejemplos de
los apuntes, y pueden leerla cuanto quieran. Está escrita para que se lea como la definición, con conjuntos de
nombres, y no para ser rápida. `solution.cpp` se escribe **sin incluir `nfa.h`**: el juez compila ese único
archivo.

El trabajo del laboratorio está en tres decisiones:

- **Cómo representar un conjunto de estados** para que compararlos y buscarlos sea barato. Con $|Q| \leq 60$,
  un conjunto cabe en un entero de 64 bits, con un bit por estado. La unión es `|` y preguntar si hay algún
  estado de aceptación es `&`.
- **Cómo saber si un subconjunto ya apareció**, para no generarlo dos veces: un `std::map` o un
  `std::unordered_map` del conjunto a su número.
- **Qué nombre darle a cada uno.** El nombre natural, $\{q_0, q_1, q_2\}$, puede pasar de 20 caracteres. Basta
  el número de orden: `s0`, `s1`, `s2`…

Los casos traen, entre otros: transiciones $\varepsilon$ en cadena y en ciclo, un NFA sin estados de aceptación,
uno con un solo estado y ninguna transición, estados inalcanzables, un DFA como entrada, un estado que se llama
`eps`, pares repartidos en varias líneas y cuatro casos grandes.

## Cómo avanzar

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

1. **Lean el NFA.** Numeren los estados y los símbolos en el orden en que aparecen, y guarden $\delta$ por
   números. Empiecen con `casos/01.in`, que no tiene transiciones $\varepsilon$.
2. **Calculen la clausura $\varepsilon$** con una búsqueda en el grafo que solo tiene las flechas
   $\varepsilon$: desde cada estado del conjunto, sigan esas flechas hasta que no aparezca ningún estado nuevo.
   Antes de programarla, calculen a mano $E(\{q_a\})$ en `casos/03.in`.
3. **Generen los subconjuntos alcanzables con una cola.** El primero es $E(\{q_0\})$. Mientras la cola no esté
   vacía, saquen un subconjunto $S$ y calculen, para cada símbolo $a$, el conjunto
   $E\bigl(\bigcup_{q \in S} \delta(q, a)\bigr)$. Si es nuevo, denle el siguiente número y pónganlo en la cola.
   El conjunto vacío es un subconjunto como cualquier otro: si aparece, es el estado trampa del DFA.
4. **Escriban el DFA** y pásenlo por el juez. Si un caso da `WA`, lean el motivo que da el verificador y sigan a
   mano la cadena que muestra.
5. **Midan** cuántos estados salen con la familia de la sección siguiente.

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

Para ver su DFA funcionando, pásenle la salida al simulador que escribieron en el laboratorio de la semana 1,
agregando el bloque de cadenas:

```sh
{ build/solution < casos/02.in; printf 'strings: 3\n0101\n0100\n\n'; } | ../../../week-01/lab/dfa_sim/build/solution
```

Debe imprimir `acepta`, `rechaza`, `rechaza`.

## El k-ésimo símbolo desde el final

El lenguaje "el $k$-ésimo símbolo desde el final es $\mathtt{1}$" tiene un NFA de $k + 1$ estados. El programa
`kth_nfa` de la carpeta de la semana lo escribe para el $k$ que le pidan. Desde `code/week-02`, después de
correr `make` ahí:

```sh
build/kth_nfa 3 | lab/nfa_to_dfa/build/solution | head -1 | wc -w
```

La primera línea de su salida es `states:` seguida de los nombres, así que la cantidad de estados es ese número
menos 1. Con $k = 3$ debe salir 9: ocho estados.

Corran su programa con $k$ de 1 a 12 y llenen la tabla:

| $k$ | Estados del NFA | Estados de su DFA |
|---|---|---|
| 1 | 2 | |
| 2 | 3 | |
| 3 | 4 | 8 |
| … | | |
| 12 | 13 | |

Después respondan:

1. ¿Qué fórmula sigue la tercera columna? Compárenla con la tabla de los apuntes, en la sección *El costo: hasta
   2ⁿ estados*.
2. Para $k = 12$ el NFA tiene 13 estados y $2^{13} = 8192$ subconjuntos. ¿Cuántos alcanzó su programa? ¿Qué
   tienen en común todos los subconjuntos alcanzables?
3. ¿Hasta qué $k$ llega su programa en 2 segundos? ¿Qué se acaba primero, el tiempo o el límite de 10 000
   estados?

## Para seguir

Opcional, sin casos en el juez.

- Escriban la construcción de la unión: un programa que lea dos NFA, uno después del otro, y escriba el NFA con
  un estado inicial nuevo y dos transiciones $\varepsilon$. Pásenlo por su `solution` y comparen la cantidad de
  estados con el producto de la semana 1.
- Su DFA puede tener estados de más: dos subconjuntos distintos a veces se comportan igual. Con `casos/12.in`,
  ¿cuántos estados produce su programa? En la semana 4 veremos cómo hallar el DFA más pequeño.
