La quíntupla: la definición formal sin misticismo

La quíntupla tiene fama de trámite: cinco letras que se recitan al principio de un capítulo y se olvidan en la página siguiente. Esa fama es injusta y sale cara. Cada uno de los cinco componentes responde a una pregunta distinta que cualquier modelo de cómputo está obligado a responder —qué situaciones existen, qué puede llegar, qué se sigue de qué, dónde se empieza y qué cuenta como éxito— y ninguno de los cinco puede quitarse sin perder algo concreto. Leerlos despacio una sola vez es lo que convierte la definición en una herramienta de diseño en lugar de un ornamento académico. Aquí la leemos despacio, sin misticismo, y sin saltarnos los matices que los libros dan por sabidos.

Cinco componentes y ni uno de adorno

Un autómata finito determinista se define como la quíntupla M = (Q, Σ, δ, q0, F). La expresión es tan compacta que invita a pasar de largo, así que conviene interrogar a cada componente y preguntarle qué aporta y qué se rompería sin él.

Q es un conjunto finito y no vacío de estados. No es una lista ordenada ni una jerarquía: es un conjunto, y por tanto sus elementos no tienen más estructura que su identidad. Que sea finito es la restricción que da nombre al modelo y la que vuelve decidible casi todo lo que querríamos preguntarle. Σ es el alfabeto: un conjunto finito y no vacío de símbolos de entrada, letras en teoría de lenguajes y nombres de eventos en una interfaz. Su finitud pesa tanto como la de Q, porque si el alfabeto fuese infinito la tabla de transiciones dejaría de ser un objeto escribible.

δ es la función de transición, con firma δ: Q × Σ → Q, y es el único componente que codifica comportamiento; los otros cuatro son inventarios. Que se la llame función y no relación es la afirmación entera del determinismo, y su peso es tal que la lección siguiente se dedica por completo a lo que ocurre cuando se relaja. q0 pertenece a Q y es el estado inicial: un elemento distinguido, no un valor por defecto, porque cambiarlo produce una máquina distinta que puede reconocer un lenguaje distinto con exactamente las mismas transiciones. Y F, subconjunto de Q, reúne los estados de aceptación.

Sobre F conviene deshacer tres supersticiones. Puede ser vacío, y entonces M no acepta ninguna cadena. Puede ser todo Q, y entonces acepta todas. Y puede contener a q0, en cuyo caso la cadena vacía pertenece al lenguaje. Los tres casos son legítimos y aparecen sin drama en construcciones reales, por ejemplo al complementar una máquina.

La separación en cinco piezas no es capricho notacional: aísla el inventario —Q y Σ—, del comportamiento —δ—, de la interpretación —q0 y F—. Dos autómatas pueden compartir los tres primeros componentes y diferir solo en los dos últimos reconociendo lenguajes distintos, y esa independencia es justo lo que explotan la minimización, el complemento y la construcción del autómata inverso.

Total, parcial y el estado sumidero

Un detalle que los textos resuelven en una nota al pie y que en la práctica decide diseños: ¿está δ definida para todos los pares de Q × Σ? Si lo está, la función es total y la máquina es completa. Si algunos pares quedan sin destino, la función es parcial y la máquina se queda atascada al recibir uno de ellos. Ambos convenios circulan en la literatura y la equivalencia entre ellos es constructiva y barata.

Para totalizar una máquina parcial se añade un estado sumidero —también llamado trampa o estado muerto— que no pertenece a F, se dirigen a él todos los pares que faltaban, y se le dan bucles sobre sí mismo para cada símbolo del alfabeto. Una vez dentro no se sale, y como no acepta, cualquier cadena que llegue allí queda rechazada para siempre. El lenguaje reconocido no cambia en absoluto: solo se ha hecho explícito el rechazo que antes era un atasco.

stateDiagram-v2
[*] --> q0
q0 --> q1 : a
q0 --> sumidero : b
q1 --> q1 : a
q1 --> q1 : b
sumidero --> sumidero : a
sumidero --> sumidero : b

Esa máquina acepta exactamente las cadenas sobre a, b que empiezan por a, con F igual a q1. Su tabla completa cabe en cuatro casillas visibles y ninguna está vacía, que es justo el punto de totalizar.

Las dos totalizaciones se distinguen en el código con la misma claridad con la que se distinguen en la pizarra, y verlas juntas evita elegir por descuido.

type Par = { estado: Estado; simbolo: Simbolo }

// Totalizacion por sumidero: lo no declarado es un rechazo irrecuperable.
const conSumidero = (p: Par): Estado => delta[p.estado]?.[p.simbolo] ?? "sumidero"

// Totalizacion por bucle: lo no declarado es un evento que se ignora.
const conBucle = (p: Par): Estado => delta[p.estado]?.[p.simbolo] ?? p.estado

La totalidad tiene además una consecuencia técnica que reaparecerá en la lección 3: complementar un autómata consiste en intercambiar F por Q menos F, y esa operación solo es correcta si la máquina es completa. Sobre una máquina parcial, intercambiar los finales produce un autómata que acepta un lenguaje equivocado, porque las cadenas atascadas no estaban siendo rechazadas por ningún estado concreto al que pudiéramos darle la vuelta.

Un tercer convenio, menos frecuente pero legítimo, es dejar δ parcial y tratar el atasco como un error de ejecución que se propaga hacia arriba. Tiene sentido cuando la entrada procede de un sistema del que se espera corrección y un símbolo inesperado indica un fallo de integración que conviene ver cuanto antes. Lo que nunca es aceptable es no haber elegido: una máquina cuyo comportamiento ante lo no declarado depende del lenguaje de implementación, del tipo de acceso a un objeto o de si alguien puso un ?. es una máquina cuya quíntupla no está realmente definida.

Aceptar una cadena: la extensión δ*

δ consume un símbolo. Para hablar de cadenas se define su extensión δ*: Q × Σ* → Q por inducción sobre la longitud: δ*(q, ε) = q para la cadena vacía, y δ*(q, wa) = δ(δ*(q, w), a) para una cadena w seguida de un símbolo a. Es decir, procesa w desde q, y desde donde acabes aplica δ una vez más.

Con δ* la aceptación deja de ser una intuición y se vuelve una definición de una línea: el lenguaje de M es el conjunto de cadenas w sobre Σ* tales que δ*(q0, w) pertenece a F. Nada más. No hay backtracking, no hay elección, no hay estados intermedios que reinterpretar: se pliega la cadena desde q0 y se mira si el estado en el que se cae está en F.

Esa inducción es, palabra por palabra, un pliegue por la izquierda. δ* no es una construcción exótica: es reduce con δ como operador y q0 como acumulador inicial, y esa identidad es la razón por la que el estado de una máquina siempre puede reconstruirse desde su historial de eventos.

Merece la pena detenerse en una propiedad de δ* que se demuestra en tres líneas por inducción y que se usa constantemente sin nombrarla: δ*(q, uv) = δ*(δ*(q, u), v). Es decir, procesar una cadena entera equivale a procesar la primera mitad y continuar con la segunda desde donde se quedó. Esa asociatividad es lo que legitima persistir el estado en lugar del historial, partir una traza en fragmentos para depurarla, o reanudar una sesión sin volver a reproducir todos los eventos desde el principio. Y es también lo que falla en cuanto la máquina consulta algo externo a δ: si el destino depende de un reloj o de una variable global, la traza deja de ser troceable porque procesar la segunda mitad más tarde ya no da el mismo resultado.

Conviene también no confundir el lenguaje de una máquina con la máquina misma. L(M) es un conjunto de cadenas y nada más; máquinas muy distintas pueden definir el mismo lenguaje, y de hecho hay infinitas máquinas por lenguaje regular, todas obtenibles añadiendo estados redundantes. Esa distinción entre el objeto sintáctico —la quíntupla— y el objeto semántico —el conjunto de cadenas— es la que abre la puerta a la minimización, y la que hace posible preguntar si dos definiciones distintas significan lo mismo. La lección 3 recoge esa pregunta y la responde con un algoritmo.

La definición convertida en tipo

Todo lo anterior cabe en un archivo de TypeScript sin perder ni una garantía, y el ejercicio de escribirlo es más instructivo de lo que parece: obliga a decidir explícitamente cosas que la notación matemática deja implícitas.

type Estado = "q0" | "q1" | "sumidero"
type Simbolo = "a" | "b"

// delta total: el Record obliga a declarar TODOS los pares estado-simbolo
const delta: Record<Estado, Record<Simbolo, Estado>> = {
  q0:       { a: "q1",       b: "sumidero" },
  q1:       { a: "q1",       b: "q1" },
  sumidero: { a: "sumidero", b: "sumidero" },
}

const inicial: Estado = "q0"
const finales: ReadonlySet<Estado> = new Set<Estado>(["q1"])

// delta* como pliegue por la izquierda sobre la cadena
const deltaEstrella = (w: Simbolo[]): Estado => w.reduce((q, s) => delta[q][s], inicial)

const acepta = (w: Simbolo[]): boolean => finales.has(deltaEstrella(w))

El tipo Record<Estado, Record<Simbolo, Estado>> no es decoración: es la totalidad de δ convertida en obligación del compilador. Si olvidas un par, el código no compila; si añades un estado a Q, el error aparece exactamente en la tabla que hay que ampliar. La definición formal, expresada así, deja de ser un recordatorio de buenas intenciones y pasa a ser una restricción mecánica, que es la única clase de restricción que sobrevive a un equipo y a un año de cambios.

Compárese con la alternativa habitual, un switch sobre el estado con un default que devuelve el estado actual. Funciona, es más corto y parece equivalente, pero ha renunciado a lo esencial: el default absorbe silenciosamente todos los pares que se olviden, de modo que añadir un estado nuevo no produce ningún error y la máquina simplemente ignora eventos que debería atender. La tabla exhaustiva convierte ese olvido en un fallo de compilación; el switch permisivo lo convierte en un comportamiento raro que aparecerá en producción. La diferencia entre ambos no es de estilo: es si el modelo formal sigue vigente o si solo queda su recuerdo.

Nótese además que ese objeto no es solo ejecutable, es inspeccionable. Se puede recorrer para listar los estados inalcanzables desde q0, para detectar estados sin salida, para generar el diagrama o para producir automáticamente un caso de prueba por cada casilla. Nada de eso es posible cuando la transición está repartida por condicionales dentro de manejadores de eventos. La quíntupla como dato, y no como código, es lo que habilita todo el utillaje que rodea a las máquinas serias: visualizadores, comprobadores de cobertura y generadores de tests basados en el modelo.