Máquinas de estados finitos

01 · Punto de partida

El problema de las banderas

Imaginá el control de un portón corredizo con un único pulsador. Una pulsación abre si está cerrado, detiene si está en movimiento, cierra si está abierto. Un fin de carrera avisa que llegó arriba o abajo, y una fotocélula detecta un obstáculo: si hay algo mientras cierra, el portón debe volver a abrir. Una primera implementación, tal como sale al principio, se ve así:

static bool abriendo, cerrando, abierto, cerrado, detenido;     /* ¿qué está pasando? */

void al_pulsar_boton(void) {
    if (abierto && !cerrando)                    { abierto = false; cerrando = true; motor_cerrar(); }
    else if (cerrado && !abriendo)               { cerrado = false; abriendo = true; motor_abrir(); }
    else if (abriendo || cerrando)                   { abriendo = cerrando = false; detenido = true; motor_parar(); }
    else if (detenido && !abierto)               { detenido = false; cerrando = true; motor_cerrar(); }
    /* ...¿y si el botón llega justo cuando termina de abrir? ¿y con el obstáculo a la vez? */
}

El código funciona en las pruebas fáciles y se rompe en las difíciles. Con cinco banderas hay 32 combinaciones posibles, pero solo cinco tienen sentido (abriendo y cerrando a la vez no existe en el mundo); las otras 27 son «imposibles» solo mientras cada if esté perfecto. Cada evento nuevo obliga a revisar todas las ramas, y nadie puede responder con seguridad «¿qué hace el portón si el obstáculo aparece mientras está detenido?» sin leer todo el código.

Una máquina de estados finitos (FSM, Finite State Machine) resuelve el problema cambiando la pregunta. En lugar de una colección de banderas, el sistema tiene una sola variable, el estado actual, que puede valer uno de un conjunto finito de valores; y el comportamiento se describe respondiendo, para cada estado y para cada evento posible, qué pasa. Es una tabla, y una tabla se puede revisar, completar y probar entera.

Este tema es de modelado: pensar con lápiz y papel antes de escribir una sola línea de control. Es la parte que más rinde, porque un error de modelado cuesta una hora de dibujo; el mismo error descubierto con el portón en marcha cuesta un portón.

02 · El vocabulario

Los elementos de una máquina de estados

Una máquina de estados tiene un puñado de piezas, y conviene usar los nombres exactos porque son los que usan los libros, las herramientas y los colegas:

Cuatro ideas que separan un buen modelo de uno mediocre:

• Un estado representa lo que el sistema necesita recordar, no lo que está haciendo. ABRIENDO es un estado porque el sistema debe recordar que el motor está subiendo (y que el próximo fin de carrera relevante es el de arriba); «el motor gira» es una consecuencia, no el estado.
• Un evento es un hecho puntual; un estado dura. «Se apretó el botón» es un evento; «el botón está apretado» es un nivel. Confundirlos es la fuente número uno de errores (apartado 5).
• La misma pulsación significa cosas distintas según el estado. Ésa es la esencia del modelo: el botón abre, detiene o cierra según dónde se esté. En el código con banderas esa dependencia está escondida en condiciones; en la máquina está a la vista.
• Un estado puede recibir un evento y no hacer nada: ignorarlo. Siempre que sea una decisión y no un olvido (apartado 6).

03 · Dos maneras de escribirla

Diagramas y tablas de transiciones

Una máquina de estados se escribe de dos formas equivalentes, y cada una responde mejor a una pregunta. El diagrama de estados muestra el recorrido: los estados son cajas, las transiciones son flechas rotuladas con evento [guarda] / acción, y un punto negro marca el estado inicial. Se lee de un vistazo la «historia» del sistema:

La tabla de transiciones es la misma máquina vista por filas y columnas: una fila por estado, una columna por evento, y en cada celda el estado al que se va (más la acción). Es menos intuitiva de leer, pero tiene una virtud que el diagrama no tiene: obliga a mirar todas las celdas, incluidas las vacías, y las vacías son donde viven los errores de diseño.

Se usan los dos juntos: el diagrama para pensar y conversar con el cliente o el equipo; la tabla para verificar que no falta nada y para programar, porque se traduce casi literalmente a código (tema 25). Cuando los dos no coinciden, el defecto está en uno de los dos, y descubrirlo antes de programar es el objetivo del modelado. Del cuadro se desprende además una cuenta útil: 5 estados por 5 eventos son 25 celdas, y el portón define 9 transiciones; hay 16 celdas que ignoran el evento, y cada una merece una mirada.

04 · Las salidas

Moore y Mealy: dónde van las salidas

Una máquina de estados no solo cambia de estado: hace cosas. La teoría distingue dos formas de asociar las salidas, y en firmware se usan las dos:

En código real se mezclan, y la regla práctica es: las salidas que representan una condición sostenida van en el estado (con acciones de entrada y de salida: «mientras esté ABIERTO, la luz está encendida»), y las que son una orden puntual van en la transición («arrancar el motor hacia arriba»). Las acciones de entrada son especialmente útiles porque evitan repetir lo mismo en cada transición que llega a un estado: si tres caminos distintos llevan a ABIERTO, el temporizador de autocierre se arranca en un solo lugar, la entrada, y no hay manera de olvidarlo en uno de los tres.

Conviene que las acciones sean breves y no bloqueantes: cambiar una salida, encolar un mensaje, armar un temporizador. Una acción que espera o hace un cálculo largo dentro de una transición congela a la máquina y a todo lo que comparta su tarea (temas 14 y 19). Lo largo se modela como un estado más: el portón no «espera a que llegue arriba» dentro de una acción, sino que está en ABRIENDO hasta que llega el evento FC_ABIERTO.

05 · La frontera con el mundo físico

De las señales a los eventos

Las máquinas de estados reciben eventos, pero el hardware entrega señales: niveles en pines, contadores que avanzan, bytes que llegan. Convertir unas en otros es un trabajo propio, y donde más se equivoca la gente:

• Nivel contra flanco. «El botón está apretado» es un nivel, que dura mientras el dedo esté sobre él; «se apretó el botón» es un evento, que ocurre una vez. Si la máquina recibiera el nivel como evento, un dedo que tarda 300 ms generaría miles de eventos a la velocidad del bucle, y el portón abriría, detendría, cerraría y abriría de nuevo. Se detecta el flanco: comparar el valor actual con el anterior.
• Rebote. Un contacto mecánico rebota unos milisegundos (tema 14). Un flanco sin filtrar son varios eventos. Se filtra antes de que la señal sea un evento: la máquina ve «un botón» limpio, no el ruido del contacto.
• El tiempo como evento. «Pasaron 10 segundos en ABIERTO» es un evento, producido por un temporizador (tema 17) que se arma en la acción de entrada del estado y se cancela en la de salida. La máquina no «cuenta»: recibe TIMEOUT.
• Mensajes y comandos que llegan por una comunicación (un comando por UART, una orden remota) son eventos con datos; el parser del tema 23 los produce.
• Eventos simultáneos. Si en el mismo instante hay un obstáculo y un pulso del botón, hay que decidir un orden. Se procesa un evento por vez, empezando por el más crítico para la seguridad: el obstáculo antes que el botón.

typedef enum { EV_NINGUNO, EV_OBSTACULO, EV_FC_CERRADO, EV_FC_ABIERTO, EV_TIMEOUT, EV_BOTON } Evento;

Evento siguiente_evento(void) {
    static bool boton_antes;
    bool boton = boton_estable();                    /* ya sin rebote (tema 14) */
    bool flanco = boton && !boton_antes;             /* solo el instante en que pasa de suelto a apretado */
    boton_antes = boton;

    if (obstaculo_detectado())        return EV_OBSTACULO;   /* la seguridad tiene prioridad sobre el usuario */
    if (fin_de_carrera_cerrado())     return EV_FC_CERRADO;
    if (fin_de_carrera_abierto())     return EV_FC_ABIERTO;
    if (temporizador_vencio())        return EV_TIMEOUT;
    if (flanco)                       return EV_BOTON;
    return EV_NINGUNO;                               /* no pasó nada: la máquina no hace nada */
}

Hay una trampa sutil en ese código: fin_de_carrera_cerrado() es un nivel (el portón sigue contra el tope mientras esté cerrado), y devolverlo en cada pasada produciría un evento FC_CERRADO permanente. La máquina del portón lo ignora en todos los estados salvo CERRANDO, y por eso no se nota; pero un diseño descuidado multiplicaría eventos sin sentido. Lo correcto es generar el evento en el flanco del fin de carrera, igual que con el botón.

Por último, la máquina procesa los eventos de a uno y hasta terminar (run to completion): cada evento ejecuta su transición completa, con sus acciones, antes de atender el siguiente. Con eso se evita que dos transiciones se pisen, y es el fundamento de la programación orientada a eventos del tema 26, donde los eventos esperan en una cola.

06 · Verificar sobre el papel

Comprobar el modelo antes de programarlo

La gran ventaja de una máquina de estados es que se puede analizar sin ejecutarla, porque es una estructura finita. Estas son las comprobaciones que conviene hacer a cualquier modelo, y que el programa de Python de este tema automatiza:

La completitud es la más rentable. De las 16 celdas que el portón ignora, no todas son iguales. Las hay legítimas: BOTON mientras ya está CERRADO y se está esperando el fin de carrera no tiene un significado distinto. Pero otras son sospechosas: ¿qué significa recibir FC_CERRADO estando ABIERTO? Físicamente es imposible, de modo que si ocurre, un sensor está fallando o está mal cableado. Ignorarlo en silencio esconde un defecto; una respuesta razonable es agregar un estado FALLO (motor apagado, aviso) al que llevan los eventos imposibles. Esa decisión no aparece nunca si no se miran las celdas vacías.

Y lo mismo con obstáculo mientras abre: ¿se detiene, se ignora? El modelo del apartado 3 lo ignora (el obstáculo es un peligro al cerrar, no al abrir), pero es una decisión de producto que debería estar escrita y firmada, no una omisión. La variante del laboratorio que ignora el obstáculo al cerrar muestra el costado peligroso del mismo mecanismo: un evento ignorado por descuido en la celda equivocada produce un portón que baja sobre un objeto.

También sirve para planificar las pruebas. Cada celda es un caso de prueba: 25 celdas, 25 casos. El análisis del programa encuentra una secuencia de eventos que las recorre todas (44 eventos para el portón) usando caminos mínimos entre estados, y esa secuencia se convierte en una prueba automática que se ejecuta en la computadora y en el equipo. Es una cobertura que con banderas sueltas es imposible de definir.

07 · Lo que sale mal

Errores de modelado

Una cuenta ayuda a entender por qué la separación importa. Dos máquinas independientes de 4 y 5 estados, si se mezclan en una sola, necesitan 4 × 5 = 20 estados combinados; si se mantienen separadas, son 4 + 5 = 9. Con tres comportamientos de 4 estados cada uno, 64 contra 12. La separación en máquinas independientes que se comunican con eventos es la herramienta principal contra la explosión.

También conviene saber cuándo no usar una máquina de estados. Si el comportamiento es un cálculo (un filtro, un controlador PI) no hay «estados» en el sentido que importa: es una función. Si es un procesamiento de datos con estructura (interpretar un protocolo complejo) puede ser mejor un analizador sintáctico. La máquina es la herramienta para comportamiento reactivo que depende de la historia.

08 · Analogía con programación

Analizar una máquina en Python

El programa representa la máquina del portón como un diccionario (estado, evento) → (estado nuevo, acción), que es exactamente la tabla del apartado 3. Con esa representación hace tres cosas: ejecuta escenarios y muestra cada transición; analiza el modelo (completitud, alcanzabilidad, trampas) y construye una secuencia de eventos que prueba todas las celdas; y cuenta cuántas combinaciones de banderas habría que gobernar si se implementara el mismo comportamiento sin máquina de estados.

from collections import deque
from itertools import product

ESTADOS = ["CERRADO", "ABRIENDO", "ABIERTO", "CERRANDO", "DETENIDO"]
EVENTOS = ["BOTON", "FC_ABIERTO", "FC_CERRADO", "OBSTACULO", "TIMEOUT"]

# (estado, evento) -> (estado nuevo, acción).  Lo que no está en la tabla es un evento que ese estado ignora.
TABLA = {
    ("CERRADO",  "BOTON"):      ("ABRIENDO", "motor_abrir"),
    ("ABRIENDO", "FC_ABIERTO"): ("ABIERTO",  "motor_parar"),
    ("ABRIENDO", "BOTON"):      ("DETENIDO", "motor_parar"),
    ("ABIERTO",  "BOTON"):      ("CERRANDO", "motor_cerrar"),
    ("ABIERTO",  "TIMEOUT"):    ("CERRANDO", "motor_cerrar"),
    ("CERRANDO", "FC_CERRADO"): ("CERRADO",  "motor_parar"),
    ("CERRANDO", "BOTON"):      ("DETENIDO", "motor_parar"),
    ("CERRANDO", "OBSTACULO"):  ("ABRIENDO", "motor_abrir"),
    ("DETENIDO", "BOTON"):      ("CERRANDO", "motor_cerrar"),
}

def procesar(estado, evento):
    """Un paso de la máquina: devuelve (estado nuevo, acción). Si el estado ignora el evento, no cambia nada."""
    return TABLA.get((estado, evento), (estado, None))

def correr(titulo, eventos, inicial="CERRADO"):
    print(titulo)
    estado = inicial
    for ev in eventos:
        nuevo, accion = procesar(estado, ev)
        if accion:
            print(f"  {estado:9s} --{ev:10s}--> {nuevo:9s}  [{accion}]")
        else:
            print(f"  {estado:9s} --{ev:10s}--> (ignorado)")
        estado = nuevo
    print(f"  estado final: {estado}\n")

print("Parte 1: la máquina del portón en acción")
correr("  Apertura y cierre normales", ["BOTON", "FC_ABIERTO", "BOTON", "FC_CERRADO"])
correr("  Obstáculo mientras cierra", ["BOTON", "FC_ABIERTO", "BOTON", "OBSTACULO", "FC_ABIERTO"])
correr("  Botón a mitad de camino, y autocierre", ["BOTON", "BOTON", "BOTON", "FC_CERRADO", "BOTON", "FC_ABIERTO", "TIMEOUT", "OBSTACULO"])

# --- Parte 2: analizar el modelo antes de programarlo -------------------------------------------
celdas = list(product(ESTADOS, EVENTOS))
definidas = [c for c in celdas if c in TABLA]
print("Parte 2: análisis de la tabla")
print(f"  celdas (estado × evento): {len(celdas)}; con transición: {len(definidas)}; ignoradas: {len(celdas) - len(definidas)}")

def alcanzables(origen):
    visto, cola = {origen}, deque([origen])
    while cola:
        s = cola.popleft()
        for (e, ev), (n, _) in TABLA.items():
            if e == s and n not in visto:
                visto.add(n); cola.append(n)
    return visto

print(f"  alcanzables desde CERRADO: {sorted(alcanzables('CERRADO'))}")
sin_retorno = [s for s in ESTADOS if "CERRADO" not in alcanzables(s)]
print(f"  estados desde los que no se puede volver a CERRADO: {sin_retorno or 'ninguno'}")
sin_salida = [s for s in ESTADOS if not any(e == s and n != s for (e, _), (n, _) in TABLA.items())]
print(f"  estados sin ninguna salida (trampas): {sin_salida or 'ninguno'}")
print("  celdas ignoradas por estado:")
for s in ESTADOS:
    ign = [ev for ev in EVENTOS if (s, ev) not in TABLA]
    print(f"    {s:9s}: {', '.join(ign)}")

# secuencia de prueba que visita las 25 celdas (cada par estado/evento al menos una vez)
def camino(origen, destino):
    previo, cola = {origen: None}, deque([origen])
    while cola:
        s = cola.popleft()
        if s == destino: break
        for ev in EVENTOS:
            n = procesar(s, ev)[0]
            if n not in previo:
                previo[n] = (s, ev); cola.append(n)
    ruta, s = [], destino
    while previo[s] is not None:
        p, ev = previo[s]; ruta.append(ev); s = p
    return ruta[::-1]

actual, prueba = "CERRADO", []
for estado, evento in celdas:
    for ev in camino(actual, estado): prueba.append(ev); actual = procesar(actual, ev)[0]
    prueba.append(evento); actual = procesar(actual, evento)[0]
print(f"  una secuencia que prueba las {len(celdas)} celdas tiene {len(prueba)} eventos")

# --- Parte 3: el mismo comportamiento con banderas sueltas ------------------------------------
banderas = ["abriendo", "cerrando", "abierto", "cerrado", "detenido"]
combinaciones = list(product([False, True], repeat=len(banderas)))
legales = [c for c in combinaciones if sum(c) == 1]
print()
print(f"Parte 3: con {len(banderas)} banderas booleanas hay {len(combinaciones)} combinaciones; solo {len(legales)} tienen sentido")
print(f"  las otras {len(combinaciones) - len(legales)} (por ejemplo 'abriendo y cerrando a la vez') deben ser imposibles a fuerza de cuidado")
for n in (5, 8, 10, 12):
    print(f"  {n:2d} banderas -> {2 ** n:5d} combinaciones posibles")

Resultado, parte 1: en el escenario normal, el portón pasa por CERRADO → ABRIENDO → ABIERTO → CERRANDO → CERRADO. Con un obstáculo mientras cierra, CERRANDO --OBSTACULO--> ABRIENDO invierte el motor y termina en ABIERTO. En el tercer escenario, el botón a mitad de camino lleva a DETENIDO y otro botón lo manda a CERRANDO; el último OBSTACULO hace volver a ABRIENDO. Parte 2: la tabla tiene 25 celdas, 9 con transición y 16 que ignoran el evento; los cinco estados son alcanzables desde CERRADO, no hay estados desde los que no se pueda volver y no hay trampas. El análisis lista las celdas ignoradas de cada estado: DETENIDO ignora cuatro eventos y CERRANDO solo dos, y es ahí donde hay que decidir si cada una es legítima o un olvido. Una secuencia de prueba que recorre las 25 celdas tiene 44 eventos. Parte 3: con 5 banderas booleanas hay 32 combinaciones, de las cuales solo 5 tienen sentido; 12 banderas serían 4096.

Probá quitar una transición de la tabla (por ejemplo, CERRANDO + OBSTACULO) y ejecutá de nuevo el escenario del obstáculo: el programa no avisará nada, porque desde el punto de vista de la máquina, ignorar es válido. Lo que sí hace es mostrarte la celda vacía. Esa es la razón de revisar las celdas, no de confiar en que el código compile.

09 · Exploración interactiva

Un portón automático

El laboratorio ejecuta la máquina del portón. Disparás eventos con los botones y ves cómo cambia el estado, qué hacen las salidas (el motor y la luz son de tipo Moore, dependen del estado) y qué registra la bitácora. La tabla de transiciones destaca la fila del estado actual. Dos opciones modifican el diseño para mostrar el efecto de las decisiones: el autocierre (que el evento TIMEOUT cierre solo desde ABIERTO) y la regla del obstáculo.

—

Recorrido guiado

1. Elegí Apertura y cierre normales y presioná «Ejecutar»: CERRADO → ABRIENDO → ABIERTO → CERRANDO → CERRADO. Observá la luz: se enciende al salir de CERRADO y se apaga al volver. El motor sube, para, baja y para: sus valores dependen solo del estado (Moore).
2. Ejecutá Obstáculo mientras cierra: en CERRANDO, el evento OBSTACULO hace pasar a ABRIENDO y el portón termina en ABIERTO. Cero eventos ignorados: el diseño tiene una respuesta para cada cosa que pasó.
3. Cambiá «Obstáculo mientras cierra» a Se ignora y repetí el escenario: el obstáculo no produce ninguna transición, el estado sigue siendo CERRANDO y el motor sigue bajando. Un aviso de peligro aparece en pantalla. Es el mismo diseño con una celda vacía por descuido, y es la clase de defecto que la revisión de completitud encuentra antes de grabar el equipo.
4. Ejecutá Botón a mitad de camino (vuelta a la opción original): el botón durante ABRIENDO lleva a DETENIDO, otro botón a CERRANDO, y recién el fin de carrera cierra. Un mismo evento, BOTON, produce acciones distintas según el estado.
5. Probá Autocierre por tiempo y después ponelo en «No»: sin autocierre, TIMEOUT en ABIERTO queda ignorado y el portón se queda abierto para siempre. No es un error del modelo, es una decisión de producto, y la tabla la muestra.
6. Ejecutá Eventos que no deberían ocurrir: FC_CERRADO estando CERRADO o FC_ABIERTO con el portón cerrando son físicamente imposibles. La tabla los ignora y el laboratorio te lo señala. Un diseño más cuidadoso los llevaría a un estado FALLO.

10 · Método de trabajo

Método para modelar

1. Escribí en prosa qué hace el dispositivo, desde el punto de vista del usuario y del mundo físico: «con el portón cerrado, un pulso abre». Cada frase es una pista de un estado o de una transición.
2. Listá los eventos. Todo lo que puede ocurrir y a lo que el sistema debe reaccionar: acciones del usuario, señales de sensores, tiempos, mensajes. Para cada uno, decidí si es un nivel o un flanco, y cómo se detecta.
3. Encontrá los estados preguntando: «¿qué necesita recordar el sistema para saber cómo reaccionar al próximo evento?». Dos situaciones que reaccionan distinto a algún evento son estados distintos; dos que reaccionan igual a todo, el mismo.
4. Elegí el estado inicial más seguro y definí qué pasa al arrancar (el estado real puede no ser el supuesto).
5. Dibujá el diagrama con las transiciones obvias, y recién entonces armá la tabla completa. Cada celda vacía recibe una decisión escrita: ignorar (¿por qué?), transición a FALLO o error.
6. Asigná las acciones: condiciones sostenidas como acciones de entrada y de salida del estado; órdenes puntuales en la transición. Todas breves y sin espera.
7. Agregá los tiempos máximos: todo estado que espera algo del mundo externo necesita un TIMEOUT o una salida.
8. Verificá las propiedades: completitud, determinismo, alcanzabilidad, ausencia de trampas, combinaciones prohibidas de salidas. Idealmente con un programa que lo haga por vos.
9. Derivá las pruebas de la tabla: una por celda, con la secuencia que las recorre. Es lo que se ejecutará contra el código.
10. Revisá el tamaño. Si hay más de unos diez estados, buscá comportamientos independientes que se puedan separar o jerarquías que simplifiquen (tema 26).

11 · Comprensión

Confusiones frecuentes

12 · Práctica guiada

Predecí antes de comprobar

1. Modelar una cerradura de código

Una cerradura abre con el código de 3 dígitos «4-2-7». Teclas posibles: dígitos del 0 al 9. Tres errores seguidos la bloquean 30 segundos. Definí los estados y los eventos, y escribí las transiciones principales.

2. Contar celdas

Una máquina tiene 6 estados y 4 eventos, y el diseño define 11 transiciones. ¿Cuántas celdas ignoran un evento? ¿Qué hacés con ellas?

3. Moore o Mealy

Clasificá: (a) «el LED está encendido mientras el estado es ABIERTO»; (b) «al recibir un obstáculo cerrando, se emite un pitido corto»; (c) «el motor sube mientras el estado es ABRIENDO».

4. ¿Evento o estado?

Clasificá como evento o como estado (nivel): (a) «el botón está apretado»; (b) «se apretó el botón»; (c) «pasaron 5 segundos»; (d) «el portón está abierto»; (e) «llegó el comando UMBRAL 25».

5. Explosión de estados

Un cargador tiene un comportamiento de carga con 4 estados (reposo, carga rápida, carga lenta, mantenimiento) y, de forma independiente, un indicador luminoso con 3 modos (fijo, parpadeo lento, parpadeo rápido). ¿Cuántos estados tendría una sola máquina que lo combine? ¿Y con dos máquinas?

6. Agregar un estado de falla

Querés que el portón vaya a un estado FALLO (motor apagado) cuando un fin de carrera se activa en un estado en el que es físicamente imposible. ¿Qué transiciones agregás y cómo se sale de FALLO?

13 · Síntesis

Ideas para recordar

¿Listo para el tema 25?

Antes de avanzar, modelá un dispositivo que tengas a mano (una lámpara con atenuador de tres niveles, una puerta de ascensor, un cargador): listá los eventos, encontrá los estados, dibujá el diagrama, completá la tabla justificando cada celda vacía y marcá qué salidas van en los estados. Si cada celda tiene una decisión escrita, el modelo está listo para programarse.

En el próximo tema vemos cómo implementar una máquina de estados en C: el switch/case, las tablas de transiciones con punteros a función, las acciones de entrada y de salida, y las buenas prácticas para que el código se parezca a la tabla que acabás de dibujar.