Qué es una máquina de estados finita

Antes de que existieran los ordenadores con memoria abundante, la teoría de la computación ya había definido su máquina más humilde: un dispositivo con un número finito de configuraciones que salta de una a otra según lo que lee. Ese autómata finito resultó ser, décadas después, la herramienta más infravalorada del desarrollo de interfaces. Su idea es casi ofensiva de tan simple: en todo momento el sistema está en un estado y solo uno, y solo un puñado de eventos declarados puede sacarlo de ahí, solo hacia destinos declarados. Todo lo que esta lección construye —y todo el nivel— sale de tomarse esa frase completamente en serio.

La quíntupla que define el modelo

En la teoría de autómatas, una máquina de estados finita determinista se define formalmente como una quíntupla M = (Q, Σ, δ, q0, F). Q es el conjunto finito de estados; Σ es el alfabeto finito de entradas —lo que en la interfaz llamamos eventos—; δ es la función de transición, el corazón de todo; q0 pertenece a Q y es el estado inicial; y F, subconjunto de Q, reúne los estados finales o de aceptación. No es folclore académico: cada pieza tiene una lectura directa en tu código.

La función de transición es la que merece atención. Su firma es δ: Q × Σ → Q: dado el estado actual y el evento que llega, devuelve el estado siguiente. Nada más. No consulta variables externas, no acumula historia, no cuenta: mira dónde estás y qué pasó, y dice a dónde vas.

type Estado = "idle" | "loading" | "success" | "error"
type Evento = "FETCH" | "RESOLVE" | "REJECT" | "RETRY"

// delta: Estado x Evento -> Estado  (la funcion de transicion)
type Transicion = (estado: Estado, evento: Evento) => Estado

Este modelo es el escalón más bajo de la jerarquía de Chomsky: reconoce exactamente los lenguajes regulares, por debajo de los autómatas con pila y de la máquina de Turing. Nace con McCulloch y Pitts en 1943, se formaliza con Kleene y alcanza su forma canónica con Rabin y Scott en 1959. Que sea el modelo más débil no es un defecto: es justo la restricción que lo vuelve analizable.

Conviene una distinción que Harel y Pnueli hicieron célebre. Un sistema transformacional recibe una entrada, calcula y termina —el autómata que valida una cadena y responde acepta o rechaza—; ahí los estados finales F importan, porque marcan el veredicto. Un sistema reactivo, en cambio, no termina: se queda a la escucha de eventos indefinidamente, como toda interfaz. En ese régimen el conjunto F suele quedar vacío o volverse anecdótico, y lo que importa es que la máquina siempre esté en un estado válido esperando el próximo evento. La FSM sirve a ambos mundos con la misma quíntupla; solo cambia el peso que tiene F. Casi todas las máquinas de una aplicación son reactivas, y por eso a menudo verás definiciones que omiten F sin remordimiento.

Una sutileza sobre q0: el estado inicial no es un valor cualquiera, es parte de la definición de la máquina. Cambiar q0 cambia la máquina, igual que cambiar una transición. En una interfaz q0 suele ser idle o un estado de carga inicial, y elegirlo mal —arrancar en success sin datos, por ejemplo— es un bug de diseño tan real como una arista equivocada, aunque se disfrace de simple valor por defecto.

“Finita”: el estado es toda la memoria

La palabra “finita” hace todo el trabajo. Q es finito y no hay nada más: la máquina no tiene contador, ni pila, ni variable auxiliar. Su memoria completa es el estado en el que se encuentra. Por eso una expresión regular —que es una FSM disfrazada— no puede emparejar paréntesis anidados a profundidad arbitraria ni validar HTML: contar requiere memoria ilimitada, y una FSM no la tiene por definición.

Lejos de ser una limitación molesta, esa cota es el regalo. Si toda la memoria del sistema es su estado actual, entonces el conjunto de situaciones posibles es enumerable y cabe en una revisión. Puedes mirar la máquina entera y preguntar, para cada estado, qué eventos acepta. El torniquete del metro es el ejemplo fundacional precisamente porque cabe en la cabeza.

stateDiagram-v2
[*] --> bloqueado
bloqueado --> desbloqueado : MONEDA
bloqueado --> bloqueado : EMPUJON
desbloqueado --> bloqueado : EMPUJON
desbloqueado --> desbloqueado : MONEDA

Dos estados, dos eventos, cuatro transiciones. La máquina no recuerda cuántas monedas metiste ni cuántas veces empujaste: su único conocimiento del mundo es si la barra está bloqueado o desbloqueado. Empujar estando bloqueado no hace nada; meter otra moneda estando desbloqueado tampoco. Esas transiciones que “vuelven al mismo sitio” son tan parte del modelo como las que cambian de estado, y declararlas explícitamente es lo que elimina la ambigüedad.

Que la máquina no tenga más memoria que su estado tiene una consecuencia operativa preciosa: reconstruir el estado actual es plegar la secuencia de eventos desde el inicial con la función de transición. No necesitas persistir el estado; te basta con el log de eventos y δ.

// el estado es un pliegue (reduce) de los eventos sobre delta
const eventos: Evento[] = ["FETCH", "REJECT", "RETRY", "RESOLVE"]
const estadoFinal = eventos.reduce(transicion, "idle")   // -> "success"

Esta propiedad es la raíz del event sourcing y del viaje en el tiempo de los depuradores: si el estado es una función pura del historial, rebobinar es volver a plegar hasta un punto anterior. La misma idea que en el nivel 8 hacía determinista la propagación reaparece aquí como reproducibilidad: dado el estado inicial y la lista de eventos, el estado final está unívocamente determinado.

Esa enumerabilidad tiene un dividendo humano que a menudo se pasa por alto: una máquina finita cabe en una revisión de código. Un revisor puede leer los estados uno a uno, recorrer las transiciones y preguntarse por cada una si es correcta, algo imposible con un enjambre de banderas cuyas combinaciones nadie ha listado jamás. Lo finito no es solo una propiedad matemática; es lo que vuelve el modelo comunicable entre personas, y por tanto revisable, discutible y mantenible.

Determinismo: una salida por cada entrada

Que δ sea una función tiene una consecuencia enorme: para cada par estado-evento hay como mucho un destino. Eso es un autómata determinista, un DFA. Su primo, el autómata no determinista o NFA, permite que un mismo par lleve a varios destinos a la vez, o que existan transiciones que no consumen entrada. El teorema de Rabin y Scott demuestra que ambos reconocen exactamente los mismos lenguajes: el no determinismo no añade poder, solo comodidad al describir ciertos patrones.

Un NFA puede, por ejemplo, ofrecer varias transiciones para el mismo evento y explorarlas todas a la vez, o incluir transiciones épsilon que cambian de estado sin consumir evento alguno. Convertirlo en el DFA equivalente puede multiplicar los estados —en el peor caso de forma exponencial, la construcción de subconjuntos—, pero el resultado es una máquina que, ante cada evento, sabe exactamente a dónde ir. Esa certeza es justo lo que una interfaz necesita y lo que la teoría de parsing puede permitirse relajar.

En la práctica del desarrollo de interfaces esto se condensa en una regla simple: define δ como una función determinista y trata cualquier evento inesperado como un no-op explícito. Esa disciplina —que el nivel 9.3 formaliza como la tabla de transiciones— convierte la reproducibilidad teórica en una garantía operativa: puedes grabar la sesión de un usuario como una lista de eventos y reproducir su bug exactamente, sin adivinar ningún estado intermedio.

Merece la pena fijar qué es un evento, porque marca la frontera con el nivel 4. Un evento es discreto y tiene nombre: FETCH, RESOLVE, un clic, la llegada de una respuesta. No es un valor que varía de forma continua como un signal, sino un suceso puntual que ocurre en un instante y dispara a lo sumo una transición. Una máquina no observa valores cambiantes; consume una secuencia de sucesos nombrados. Por eso el vocabulario importa: los eventos se nombran como algo que pasó o una orden que se da, y jamás describen el estado, que es competencia exclusiva de Q.

Mealy y Moore: dónde vive la salida

Un autómata que solo reconoce no basta para una interfaz: necesitamos que además haga cosas —lanzar una petición, enfocar un campo—. Ahí entran los dos modelos clásicos de máquina con salida. En una máquina de Moore, la salida depende únicamente del estado en el que estás: al entrar en loading, disparas la petición. En una máquina de Mealy, la salida depende del estado y del evento juntos, es decir, va pegada a la transición: al ir de idle a loading por el evento FETCH, ejecutas la acción.

Son equivalentes en poder expresivo —cualquier máquina de Mealy se traduce a una de Moore y viceversa— y difieren solo en ergonomía. Los motores modernos ofrecen las dos: las acciones entry y exit, ligadas al estado, son estilo Moore; las acciones colgadas de una transición concreta son estilo Mealy. Saber cuál es cuál te evita el error clásico de disparar un efecto en la transición cuando querías dispararlo en cada entrada al estado, sin importar de dónde vinieras.

Un ejemplo diminuto fija la diferencia. Al modelar un menú desplegable, enfocar el primer elemento al abrir es Moore —ocurre por estar en abierto, vengas del teclado o del ratón—, mientras que reproducir un sonido solo al abrir con teclado es Mealy —depende del evento concreto que provocó la transición—.

const desplegable = {
  cerrado: {
    on: {
      ABRIR_RATON:   { destino: "abierto" },
      ABRIR_TECLADO: { destino: "abierto", accion: "sonar" },  // Mealy: en la transicion
    },
  },
  abierto: {
    entry: "enfocarPrimero",   // Moore: al entrar, venga de donde venga
    on: { CERRAR: { destino: "cerrado" } },
  },
}