DFA y NFA: la diferencia y la equivalencia

El no determinismo suena a que la máquina decide al azar, y no es eso en absoluto. Un autómata no determinista no elige: explora todas las alternativas a la vez y acepta si alguna de ellas llega a buen puerto. Esa lectura —angelical, se la llama— es lo que lo convierte en un lenguaje de descripción tan cómodo, porque permite escribir lo que se quiere reconocer sin explicar cómo distinguirlo paso a paso. Y luego llega el resultado que ordena todo el campo: esa comodidad no compra ni un lenguaje más. Cualquier NFA tiene un DFA equivalente, y la diferencia entre ambos no es de poder sino de tamaño y de quién carga con el trabajo de decidir.

Relajar la función hasta convertirla en relación

En un DFA, δ: Q × Σ → Q devuelve exactamente un destino. Un autómata finito no determinista relaja esa firma a δ: Q × Σ → P(Q), donde P(Q) es el conjunto de partes de Q. El resultado ya no es un estado sino un conjunto de estados, posiblemente vacío y posiblemente con varios elementos. Con el conjunto vacío se recupera la máquina parcial de la lección anterior; con conjuntos de dos o más elementos aparece el no determinismo genuino.

La definición de aceptación cambia en consecuencia y es aquí donde está toda la sutileza. Un NFA acepta una cadena si existe al menos un camino, entre todos los posibles, que la consuma entera y termine en un estado de F. No importa que otros mil caminos mueran o acaben en estados no aceptadores: basta uno. Esa cuantificación existencial es lo que se llama no determinismo angelical, y es la razón por la que un NFA es tan fácil de escribir: describes las formas de tener éxito y no te ocupas de descartar las de fracasar.

stateDiagram-v2
[*] --> s0
s0 --> s0 : a
s0 --> s0 : b
s0 --> s1 : a
s1 --> s2 : b
s2 --> [*]

Ese NFA reconoce las cadenas que terminan en ab, y merece la pena ver por qué es tan cómodo. Desde s0 el símbolo a lleva a la vez a s0 y a s1: la máquina, informalmente, apuesta a que esa a es la penúltima letra sin dejar de contemplar que no lo sea. Escribir el DFA equivalente exige llevar la cuenta explícita del sufijo leído y produce estados con una interpretación mucho menos evidente. Tres estados y una arista ambigua sustituyen a un razonamiento que a mano cuesta bastante más.

Existe además una variante con transiciones épsilon, cuya firma es δ: Q × (Σ ∪ {ε}) → P(Q): aristas que cambian de estado sin consumir ningún símbolo. Sirven para pegar autómatas entre sí sin retocar sus aristas, y son el pegamento con el que la construcción de Thompson traduce una expresión regular en un NFA. Su tratamiento se resume en una operación: la clausura épsilon de un conjunto de estados es ese conjunto ampliado con todo lo alcanzable por aristas épsilon, aplicado hasta punto fijo. Con la clausura, las transiciones épsilon se eliminan sin cambiar el lenguaje, y por eso no aportan poder tampoco.

La construcción de subconjuntos

Michael Rabin y Dana Scott formalizaron en 1959 la equivalencia, y su demostración es constructiva: dado un NFA, se fabrica un DFA que reconoce el mismo lenguaje. La idea es la del párrafo anterior llevada al extremo lógico. Si en cada instante lo relevante es el conjunto de estados activos del NFA, entonces se toma ese conjunto como un único estado del DFA. Los estados del nuevo autómata son subconjuntos del viejo, y de ahí el nombre.

Los cinco componentes salen solos. El conjunto de estados del DFA es P(Q), o mejor, la parte de P(Q) que resulta alcanzable. Su estado inicial es la clausura épsilon del conjunto que contiene solo a q0. Su transición, dado un conjunto S y un símbolo a, es la clausura épsilon de la unión de δ(q, a) para todo q de S. Y sus estados de aceptación son los subconjuntos que contienen al menos un estado de F del NFA, que es la traducción literal de aquel existe al menos un camino.

type EstadoN = string
type NFA = {
  delta: (q: EstadoN, s: string) => EstadoN[]
  epsilon: (q: EstadoN) => EstadoN[]
  inicial: EstadoN
  finales: ReadonlySet<EstadoN>
}

// clausura epsilon: punto fijo de seguir aristas que no consumen simbolo
function clausura(n: NFA, conjunto: EstadoN[]): EstadoN[] {
  const vistos = new Set(conjunto)
  const pila = [...conjunto]
  while (pila.length) {
    const q = pila.pop() as EstadoN
    for (const r of n.epsilon(q)) if (!vistos.has(r)) { vistos.add(r); pila.push(r) }
  }
  return [...vistos].sort()
}

// un paso del DFA: el subconjunto sucesor de un subconjunto
const paso = (n: NFA, s: EstadoN[], sim: string): EstadoN[] =>
  clausura(n, [...new Set(s.flatMap((q) => n.delta(q, sim)))])

El resultado es un autómata determinista en sentido pleno: cada par subconjunto-símbolo tiene un único subconjunto sucesor. Nótese que el conjunto vacío es un subconjunto perfectamente legítimo y funciona como el estado sumidero de la lección anterior, porque desde el vacío la unión de destinos vuelve a ser vacía y ningún subconjunto vacío contiene estados de F. La totalidad aparece gratis, sin añadir nada a mano.

La demostración de que el lenguaje no cambia es una inducción sobre la longitud de la cadena y cabe en una frase: tras leer un prefijo, el subconjunto en el que está el DFA es exactamente el conjunto de estados en los que el NFA podría estar. Con esa invariante, aceptar en el DFA —que el subconjunto corte a F— equivale literalmente a que exista un camino aceptador en el NFA, que era la definición de aceptación no determinista. Lo que en el NFA era una cuantificación existencial sobre caminos se convierte en una pertenencia a un conjunto, y de ahí viene todo el ahorro.

En la práctica la construcción se implementa por exploración desde el subconjunto inicial, generando sucesores y descubriendo estados nuevos a medida que aparecen, exactamente como un recorrido en anchura sobre un grafo cuyos nodos se van inventando. Ese detalle importa: nunca se enumera P(Q) entero, solo la parte alcanzable, y por eso la construcción es utilizable en casos reales pese a que su cota teórica asuste.

El precio: la explosión exponencial y su inevitabilidad

Si el NFA tiene n estados, el DFA construido tiene como mucho 2^n. En la práctica la cifra es casi siempre mucho menor, porque solo se generan los subconjuntos alcanzables desde el inicial y la mayoría de las combinaciones no lo son. Pero esa cota no es un artefacto de una construcción torpe: existen lenguajes para los que ningún DFA puede hacerlo mejor.

El testigo canónico es el lenguaje de las cadenas sobre a, b cuyo k-ésimo símbolo contando desde el final es una a. Un NFA lo resuelve con k + 1 estados: adivina cuándo empieza el sufijo relevante y comprueba que tiene la longitud correcta. Cualquier DFA que lo reconozca necesita al menos 2^k estados, y el argumento es limpio: la máquina está obligada a recordar los últimos k símbolos leídos, porque dos prefijos que difieran en alguno de ellos pueden completarse hasta cadenas con veredictos opuestos. Como hay 2^k posibles ventanas de k símbolos y todas son distinguibles entre sí, hacen falta al menos 2^k estados para no confundirlas.

Puesto en una tabla, el reparto de virtudes queda claro y explica por qué ninguno de los dos modelos ha desplazado al otro en setenta años.

Esa asimetría explica el diseño de las herramientas reales. Un motor de expresiones regulares como RE2 o el de Rust compila el patrón a un NFA con la construcción de Thompson y después lo determiniza, pero lo hace de forma perezosa: construye cada subconjunto la primera vez que hace falta y lo cachea, de modo que solo paga por los estados que la entrada concreta visita. Así conserva la garantía de tiempo lineal en la longitud del texto sin pagar por adelantado un DFA que podría ser astronómico. Es la ingeniería exacta de esta lección puesta en producción.

Qué se lleva de aquí un motor de interfaz

Una interfaz no puede permitirse el no determinismo, y la razón no es teórica sino de depuración. La propiedad que hace reproducible un bug es que el mismo evento, en el mismo estado, lleve siempre al mismo sitio: con ella, el registro de eventos de una sesión reconstruye el estado exactamente y el fallo se repite a voluntad. Un motor no determinista rompería esa promesa de la peor manera posible, con un usuario que repite sus pasos y a veces acaba en otro lugar.

Ahora bien, en un statechart real la definición sí permite escribir algo que parece un NFA: varias transiciones candidatas para el mismo evento desde el mismo estado, cada una con su guarda. La aparente ambigüedad se resuelve por una regla de desempate declarada en la especificación, que evalúa las candidatas en orden de documento y toma la primera cuya guarda se cumple. El efecto es que la comodidad descriptiva del no determinismo se conserva —escribes las alternativas sin ordenar mentalmente todos los casos— mientras la ejecución sigue siendo una función.

// Varias candidatas para el mismo evento: se elige la primera cuya guarda pasa.
const enviando = {
  on: {
    RESPUESTA: [
      { guard: "esExito",     target: "hecho" },
      { guard: "esReintenta", target: "esperando" },
      {                        target: "fallido" },   // caso por defecto
    ],
  },
}

Esa última entrada sin guarda no es un detalle de estilo: es lo que hace total la transición. Sin ella, un evento cuyas guardas fallen todas deja la máquina donde estaba, y el diseñador debe decidir conscientemente si eso es un no-op deseado o un caso olvidado. Es, otra vez, la elección entre bucle y sumidero de la lección anterior, ahora disfrazada de rama por defecto.

Conviene señalar que ese desempate por orden documental tiene un coste real, aunque pequeño: la semántica de la máquina depende de cómo esté escrita, no solo de qué declara. Reordenar dos ramas cuyas guardas se solapan cambia el comportamiento sin cambiar ninguna condición, y ese es exactamente el tipo de cambio que una revisión de código deja pasar. La disciplina que lo evita es escribir guardas mutuamente excluyentes siempre que se pueda, de modo que el orden sea irrelevante y el desempate no llegue a usarse nunca. Cuando el solapamiento es deliberado —el caso típico de una rama general precedida por otra más específica—, merece un comentario que lo diga, porque de otro modo el siguiente lector lo tomará por casualidad.

Hay una segunda forma de no determinismo que un motor de statecharts sí prohíbe de raíz, y es útil saber por qué. Dos transiciones que compiten desde estados distintos de la misma jerarquía —una en el hijo y otra en el padre— también podrían dispararse a la vez, y la especificación resuelve el conflicto dando prioridad a la más interna. Ahí no hay ambigüedad que negociar: la regla forma parte del formalismo y no del documento. Entre ambas reglas, el orden documental para hermanas y la prioridad del más interno para ancestros, el motor recupera una δ que es función en todos los casos, que era la condición de partida.