Máquinas de estados finitos

01 · Punto de partida

Un modelo para todos los circuitos secuenciales

Desde el tema 1 el curso viene repitiendo la misma estructura: un conjunto de flip-flops que recuerda algo y una lógica combinacional que decide qué hacer con lo recordado y con lo que llega. Un contador recuerda cuántos pulsos hubo; un registro de desplazamiento, los últimos n bits; un anillo, en qué paso está. En todos los casos el circuito se describe igual: estado actual + entradas → próximo estado + salidas.

La máquina de estados finitos pone nombre y notación a esa estructura. Su ventaja es que permite pensar en comportamiento antes que en compuertas: se dibuja qué debe pasar, se verifica en papel y recién después se elige cómo implementarlo con flip-flops (tema 24) o con código. Es, además, un modelo que los programadores ya usan sin saberlo: un analizador léxico, un protocolo de red, un menú con pantallas y un videojuego con estados «jugando / pausa / game over» son máquinas de estados.

El registro de estado son los flip-flops D de los temas 8 y 13; la lógica de próximo estado, un circuito combinacional del curso anterior. Lo único nuevo es la forma de describir el conjunto.

02 · Definición

Los elementos de una FSM

Una máquina de estados finitos síncrona se define con seis cosas. Todas son finitas; de ahí el nombre.

El estado es la memoria de la máquina, y la clave está en elegirlo bien: debe contener justo lo necesario del pasado para decidir el futuro, ni más ni menos. El torniquete no necesita saber cuántas monedas entraron ni cuántas personas pasaron: le basta con saber si la barra está bloqueada o libre. Dos historias distintas que llevan al mismo estado son, para la máquina, indistinguibles.

«Síncrona» quiere decir que todo cambia en el flanco del reloj (tema 3): entre flancos, las entradas pueden variar sin efecto. En cada flanco ocurre una sola cosa: la máquina mira el estado actual y las entradas, y pasa al próximo estado. Es la misma regla de siempre: los flip-flops capturan lo que había antes del flanco.

03 · Notación gráfica

El diagrama de estados

La forma más intuitiva de describir una FSM es dibujarla. Las convenciones son pocas:

• Cada estado es un círculo con su nombre.
• Cada transición es una flecha de un estado a otro (o a sí mismo, en cuyo caso es un lazo), con una etiqueta entrada / salida.
• Una flecha que viene de afuera y apunta a un estado marca el estado inicial.

La salida escrita en la flecha depende de la transición (es una máquina de Mealy, que veremos en el tema 23); si la salida dependiera solo del estado se escribiría dentro del círculo (máquina de Moore). Por ahora alcanza con entender que la salida es parte de la especificación.

Dos reglas que todo diagrama debe cumplir

1. Completitud: de cada estado sale una flecha para cada valor posible de las entradas. Si falta alguna, el circuito real hará algo (no puede no hacer nada) y no se sabe qué.
2. Determinismo: de cada estado sale una sola flecha por cada valor de las entradas. Dos flechas con la misma entrada y destinos distintos serían una contradicción: el circuito no puede estar en dos estados a la vez.

En el torniquete, cada estado tiene tres entradas posibles (nada, moneda, empujar) y exactamente tres flechas que salen: lo cumple. Una trampa frecuente es el lazo olvidado, la transición en la que «no pasa nada»: también hay que dibujarla.

04 · Notación en tabla

La tabla de transición

El diagrama es cómodo para pensar; la tabla es cómoda para verificar y para implementar. Tiene una fila por cada par (estado, entrada) y columnas para el próximo estado y la salida. Del diagrama del torniquete sale directamente:

Comprobar que la especificación es completa es contar filas: con S estados y k valores de entrada, la tabla debe tener exactamente S · k filas. Una máquina con 5 estados y 3 entradas tiene 15 filas; con dos entradas binarias (4 combinaciones), 20. Si faltan filas, falta definir algo; si sobran, hay una contradicción.

Agrupar y usar «no importa»

Cuando varias entradas producen lo mismo, se las puede agrupar. En el torniquete, el estado Libre responde igual a «nada» y «moneda»: una sola fila con la entrada «nada o moneda» lo resume. Y cuando una combinación de entradas es físicamente imposible (por ejemplo, que llegue una moneda y una persona empuje a la vez, si el mecanismo lo impide), el próximo estado es un «no importa» (X): el diseñador queda libre de elegir lo que simplifique el circuito. Es el mismo recurso de los mapas de Karnaugh del curso de electrónica digital.

05 · Método

Especificar desde un enunciado

Pasar de un texto a un diagrama suele ser el paso más difícil. Un método que funciona casi siempre:

1. Definí entradas y salidas. Qué señales llegan, qué valores toman en cada flanco, qué debe producir la máquina.
2. Descubrí qué hay que recordar. Preguntate: «con lo que pasó hasta ahora, ¿qué necesito saber para decidir lo que viene?». Cada respuesta distinta es un estado.
3. Empezá por el estado inicial. Dibujalo y, para cada entrada posible, trazá la flecha: a qué situación lleva y qué salida produce.
4. Seguí con los estados nuevos. Cada vez que una flecha lleva a una situación no dibujada, agregá el estado y completá sus flechas.
5. Revisá la completitud y el determinismo. Contá las filas de la tabla.
6. Probá con casos. Recorré el diagrama con secuencias de entrada típicas y límite (un caso normal, uno raro, uno vacío).

Ejemplo: una máquina expendedora

Enunciado: una máquina vende un producto de 15 centavos. Acepta monedas de 5 y de 10. Cuando el dinero acumulado llega o supera los 15, entrega el producto y empieza de nuevo (no devuelve vuelto).

• Entradas: en cada flanco, una de tres: nada, moneda de 5, moneda de 10.
• Salida: ENTREGA (1 bit).
• Qué recordar: solo el dinero acumulado que todavía no alcanza para el producto: 0, 5 o 10. No importa cómo se llegó a 10 (dos monedas de 5 o una de 10). Tres estados.

Fijate en cómo se eligieron los estados: no hay uno por cada «historia de monedas» sino uno por cada saldo posible. Si el precio fuera 20 centavos, los estados serían 0, 5, 10 y 15. La cantidad de estados crece con el precio, no con la longitud de las secuencias de monedas.

06 · Verificación

Alcanzables, equivalentes y completas

Una vez escrita la tabla, tres controles mecánicos la validan:

Estados inalcanzables y estados sumidero

Un estado inalcanzable no cuesta en comportamiento (nunca se visita), pero sí en circuito: ocupa una combinación de bits. Peor es un estado sumidero (trap state): uno al que se entra pero del que no se sale, como el 0000 de un anillo mal arrancado (tema 21). Una máquina atrapada deja de responder hasta el próximo reset.

Estados equivalentes

Dos estados son equivalentes si desde cualquiera de los dos, ante cualquier secuencia de entradas, la máquina produce las mismas salidas. El caso sencillo se detecta mirando las filas: mismas salidas y mismos destinos (o destinos equivalentes entre sí). Fusionarlos no cambia el comportamiento externo y reduce la cantidad de estados. Como n flip-flops codifican hasta 2ⁿ estados, pasar de 5 a 4 estados baja la cuenta de 3 a 2 flip-flops, un ahorro real.

Lo habitual es que la reducción de estados se haga con un método sistemático (la tabla de implicantes o el algoritmo de partición), cuyo detalle excede este curso. Alcanza con saber qué se busca y revisar a ojo los casos evidentes.

07 · Implementación

Del modelo al circuito y al software

Al circuito

La especificación se vuelve circuito en cuatro pasos, que son el tema 24:

1. Se codifican los estados con bits. Para S estados hacen falta ⌈log₂ S⌉ flip-flops.
2. Se escribe la tabla en binario (estado y entradas en bits, próximo estado y salidas en bits). Las combinaciones que no ocurren quedan como «no importa».
3. Se obtienen las ecuaciones de la lógica de próximo estado y de salida.
4. Se agrega un reset que lleve a los flip-flops al estado inicial (tema 10).

El torniquete tiene 2 estados (1 flip-flop) y 3 entradas (2 bits): su tabla binaria tiene 2¹⁺² = 8 filas, de las cuales 2 son combinaciones que no ocurren.

Al software

La traducción a código es directa y es una de las maneras más limpias de organizar un programa con comportamiento dependiente del historial:

• Con una tabla: un diccionario (estado, entrada) → (próximo, salida) y un bucle que lo consulta. Es lo más cercano al modelo; completar o corregir la máquina es editar datos.
• Con switch sobre el estado: cada caso trata las entradas de ese estado. Es más eficiente y común en firmware, pero conviene mantener la tabla como documentación.

En ambos casos se aplica la regla que distingue una FSM de un programa cualquiera: una transición por flanco, decidida con el estado de antes. Si el código actualiza el estado y después lee entradas con el estado ya modificado, ya no es la misma máquina.

08 · La FSM en código

Ejecutar, verificar y codificar

Los bloques ejecutan el torniquete a partir de su tabla, la expendedora con distintas secuencias de monedas, un verificador automático de completitud, alcanzabilidad y equivalencia, y la codificación en bits del torniquete con sus «no importa».

Paso 1: el torniquete a partir de su tabla

class FSM:
    """Máquina de estados: tabla (estado, entrada) -> (próximo estado, salida)."""

    def __init__(self, tabla, inicial):
        self.tabla, self.estado = tabla, inicial

    def reloj(self, entrada):
        proximo, salida = self.tabla[(self.estado, entrada)]      # se decide con el estado ACTUAL y la entrada
        self.estado = proximo
        return salida


TORNIQUETE = {
    ("Bloqueado", "nada"):    ("Bloqueado", "-"),
    ("Bloqueado", "moneda"):  ("Libre",     "destraba"),
    ("Bloqueado", "empujar"): ("Bloqueado", "alarma"),
    ("Libre",     "nada"):    ("Libre",     "-"),
    ("Libre",     "moneda"):  ("Libre",     "-"),
    ("Libre",     "empujar"): ("Bloqueado", "traba"),
}
m = FSM(TORNIQUETE, "Bloqueado")
entradas = ["nada", "empujar", "moneda", "nada", "empujar", "empujar", "moneda", "moneda", "empujar"]
print("reloj  entrada   estado antes -> después     salida")
for k, e in enumerate(entradas, 1):
    antes = m.estado
    salida = m.reloj(e)
    print(f"{k:3d}    {e:8s}  {antes:9s} -> {m.estado:9s}   {salida}")

La secuencia muestra los tres comportamientos: empujar con la barra bloqueada dispara la alarma (reloj 2 y 6); una moneda la destraba (3 y 7); empujar con la barra libre la traba (5 y 9). Una segunda moneda con el torniquete libre no cambia nada (reloj 8). Todo el comportamiento está en la tabla: la clase no sabe nada del torniquete.

Paso 2: la máquina expendedora

# Máquina expendedora: producto de 15; acepta monedas de 5 y de 10. Estado = dinero acumulado.
TABLA = {
    (0, "nada"): (0, "-"),  (0, "5"): (5, "-"),        (0, "10"): (10, "-"),
    (5, "nada"): (5, "-"),  (5, "5"): (10, "-"),       (5, "10"): (0, "ENTREGA"),
    (10, "nada"): (10, "-"), (10, "5"): (0, "ENTREGA"), (10, "10"): (0, "ENTREGA (sobra 5)"),
}


def correr(entradas):
    estado, entregas, log = 0, 0, []
    for e in entradas:
        proximo, salida = TABLA[(estado, e)]
        log.append(f"{estado:2d} --{e}/{salida}--> {proximo}")
        if salida.startswith("ENTREGA"):
            entregas += 1
        estado = proximo
    return estado, entregas, log


casos = {
    "5, 5 (falta dinero)": ["5", "5"],
    "5, 5, 5":          ["5", "5", "5"],
    "10, 5":            ["10", "5"],
    "5, 10":            ["5", "10"],
    "10, 10":           ["10", "10"],
    "5, nada, nada, 10": ["5", "nada", "nada", "10"],
}
for nombre, secuencia in casos.items():
    estado, entregas, log = correr(secuencia)
    print(f"{nombre:20s} -> entregas: {entregas}, estado final: {estado}")
print()
print("detalle de '5, 5, 5':")
for linea in correr(["5", "5", "5"])[2]:
    print("  ", linea)

Con dos monedas de 5 la máquina queda esperando en el estado 10 y no entrega. Todas las demás secuencias entregan una vez y vuelven al estado 0; las pausas («nada») no cambian nada. El detalle de 5, 5, 5 recorre 0 → 5 → 10 → 0 con la entrega en la última transición. Probá agregar una moneda de 20 (nueva entrada): te faltarán tres filas en la tabla.

Paso 3: un verificador de especificaciones

tabla = {                                   # (estado, entrada) -> (próximo, salida)
    ("A", 0): ("B", 0), ("A", 1): ("C", 0),
    ("B", 0): ("A", 1), ("B", 1): ("C", 0),
    ("C", 0): ("D", 0),                     # falta ("C", 1)
    ("D", 0): ("A", 1), ("D", 1): ("C", 0),
    ("E", 0): ("A", 0), ("E", 1): ("E", 0), # nadie llega a E
}
estados = sorted({s for s, _ in tabla} | {p for p, _ in tabla.values()})
entradas = sorted({e for _, e in tabla})
inicial = "A"

faltan = [(s, e) for s in estados for e in entradas if (s, e) not in tabla]
print("transiciones que faltan:", faltan or "ninguna")

alcanzados, pendientes = {inicial}, [inicial]
while pendientes:
    s = pendientes.pop()
    for e in entradas:
        if (s, e) in tabla and tabla[(s, e)][0] not in alcanzados:
            alcanzados.add(tabla[(s, e)][0])
            pendientes.append(tabla[(s, e)][0])
print("estados alcanzables desde", inicial + ":", sorted(alcanzados))
print("estados inalcanzables:", sorted(set(estados) - alcanzados) or "ninguno")

firma = {}
for s in estados:
    fila = tuple(tabla.get((s, e)) for e in entradas)
    firma.setdefault(fila, []).append(s)
iguales = [g for g in firma.values() if len(g) > 1]
print("estados con filas idénticas (candidatos a fusionar):", iguales or "ninguno")

El verificador encuentra los tres defectos plantados: falta la transición (C, 1); el estado E es inalcanzable desde A; y B y D tienen filas idénticas (misma salida y mismos destinos), así que se pueden fusionar. Arreglando eso, la máquina queda con A, B y C: 3 estados que caben en 2 flip-flops en lugar de los 5 que habrían sido 3. Es el tipo de revisión que conviene hacer antes de pasar a flip-flops.

Paso 4: codificar en bits

from math import ceil, log2

estados = ["Bloqueado", "Libre"]
entradas = ["nada", "moneda", "empujar"]
n_ff = max(1, ceil(log2(len(estados))))
n_in = ceil(log2(len(entradas)))
print(f"{len(estados)} estados -> {n_ff} flip-flop(s); {len(entradas)} entradas -> {n_in} bits de entrada")
print(f"filas de la tabla en binario: 2^({n_ff}+{n_in}) = {2 ** (n_ff + n_in)}")

cod_estado = {"Bloqueado": 0, "Libre": 1}
cod_entrada = {"nada": 0b00, "moneda": 0b01, "empujar": 0b10}
tabla = {
    ("Bloqueado", "nada"): "Bloqueado", ("Bloqueado", "moneda"): "Libre", ("Bloqueado", "empujar"): "Bloqueado",
    ("Libre", "nada"): "Libre", ("Libre", "moneda"): "Libre", ("Libre", "empujar"): "Bloqueado",
}
print()
print("Q  I1 I0 | Q+")
for q in (0, 1):
    for i in range(4):
        nombre_q = estados[q]
        nombre_i = next((k for k, v in cod_entrada.items() if v == i), None)
        if nombre_i is None:
            print(f"{q}   {i >> 1}  {i & 1} | X   (combinación que no ocurre)")
        else:
            print(f"{q}   {i >> 1}  {i & 1} | {cod_estado[tabla[(nombre_q, nombre_i)]]}")

Con dos estados alcanza un flip-flop, y con tres entradas hacen falta dos bits, así que la tabla binaria tiene 8 filas y 2 de ellas (con I1 I0 = 11) son «no importa». De la tabla se lee Q⁺: pasa a 1 con una moneda, se mantiene en 1 con «nada» y se apaga con «empujar». Este es el punto de partida del diseño del tema 24.

Los cuatro bloques cubren el ciclo completo de una FSM: especificarla como datos, ejecutarla, verificarla y prepararla para convertirla en circuito.

09 · Exploración interactiva

El laboratorio: simulador de FSM

El simulador carga tres máquinas completas (el torniquete, la expendedora de 15 centavos y un detector de paridad de unos). Elegís la entrada que llega en el próximo flanco y presionás «Flanco de reloj». El diagrama marca el estado actual y la transición que se va a tomar (con su salida); la tabla resalta la fila correspondiente. El panel cuenta cuántos estados distintos se visitaron.

Recorrido guiado

1. Con el torniquete en Bloqueado, elegí «nada» y presioná «Flanco de reloj»: sigue Bloqueado, sin salida. En la tabla se resalta la fila (Bloqueado, nada).
2. Elegí «moneda» y avanzá: pasa a Libre con la salida «destraba». Elegí «empujar» y avanzá: vuelve a Bloqueado con «traba».
3. Con Bloqueado, elegí «empujar» y avanzá: se queda en Bloqueado y produce «alarma». Una transición en la que el estado no cambia puede tener salida.
4. Cambiá a la expendedora y avanzá con 5, 5 y 5: pasa por 5, 10 y vuelve a 0 con «ENTREGA». Los tres estados quedan visitados.
5. Reiniciá y probá 10 y luego 10: la segunda moneda entrega con «sobra 5». El vuelto no está en la especificación: el dinero extra se pierde, una decisión que hay que tomar al escribir el enunciado.
6. Cambiá a la paridad y avanzá con 1, 1, 0, 1: pasa a Impar, Par, Par, Impar. El estado resume en un bit toda la historia que importa.
7. Con cualquier máquina, presioná «Reset al estado inicial»: vuelve al estado de partida y los estados visitados se reinician.
8. Mirá «Estados visitados» al terminar cada recorrido: si en la torniquete no pasaste por Libre, ese estado queda sin visitar, pero sigue existiendo en la especificación.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Predecí antes de simular

1. Contar filas

Una máquina tiene 5 estados. ¿Cuántas filas debe tener su tabla de transición si tiene una entrada con 3 valores? ¿Y con dos entradas binarias independientes?

2. Seguir el torniquete

El torniquete está en Bloqueado y recibe, en orden, empujar, moneda, moneda, empujar, nada. ¿Cuáles son los estados y las salidas?

3. Cuántos flip-flops

Una máquina tiene 5 estados, de los cuales dos tienen filas idénticas. ¿Cuántos flip-flops necesita antes y después de fusionarlos?

4. Precio distinto

La expendedora vende ahora un producto de 20 con monedas de 5 y 10. ¿Cuántos estados hacen falta y cuántas filas tiene la tabla?

5. Paridad

El detector de paridad de unos recibe 1, 0, 1, 1, 1, 0 desde el estado Par. ¿En qué estado termina y qué salida produce el último flanco?

6. Diagnóstico

Una máquina de control a veces «se cuelga»: deja de responder a las entradas hasta que se reinicia. En su tabla hay un estado al que se entra con una combinación rara y desde el cual todas las entradas llevan al mismo estado. ¿Qué es y cómo se evita?

12 · Síntesis

Ideas para recordar

¿Listo para el tema 23?

Antes de avanzar, dibujá de memoria el diagrama del torniquete, contá cuántas filas tiene su tabla y explicá qué controles hay que hacer antes de pasar una especificación a flip-flops. Si podés justificar las tres respuestas, ya podés distinguir cuándo cambian las salidas.

En el próximo tema veremos los modelos de Moore y Mealy: las dos formas de asociar una salida a la máquina (al estado o a la transición), cuándo cambian las salidas en cada una y cómo evitar los pulsos indeseados.