Máquinas de estados

El panorama: máquinas con memoria del pasado

Imagina un interruptor de luz con un solo botón. Cada vez que lo presionas, la luz cambia. Presionar el mismo botón hace cosas distintas según la situación: si la luz está apagada se enciende, si está encendida se apaga. La máquina no necesita recordar todo lo que pasó. Necesita recordar una sola cosa: ¿la luz está encendida o apagada? Esa cosa es su estado.

Una máquina de estados finita tiene un número limitado (finito) de estados y ninguna otra memoria. Es un límite fuerte, y por eso algunas tareas piden máquinas más potentes. Esta área sube una escalera de máquinas, cada una con más memoria que la anterior.

  autómata finito    solo sus estados
        |
  autómata de pila   estados + una pila
        |
  máquina de Turing  estados + una cinta sin fin

  más memoria  =  más problemas resueltos

Las máquinas de estados tienen dos vidas. En la teoría son modelos: preguntamos qué conjuntos de palabras (llamados lenguajes) puede reconocer cada máquina. En la práctica son una herramienta de diseño: si listas los estados de un pedido, de una conexión o de una pantalla, las situaciones imposibles se vuelven imposibles de escribir en el código.

Palabras que vas a encontrar

• Alfabeto (Σ): el conjunto de símbolos que la máquina puede leer, por ejemplo {a, b} o {0, 1}.
• Cadena (o palabra): una fila finita de símbolos del alfabeto, como abba. La cadena vacía, escrita ε (épsilon), no tiene ningún símbolo.
• Lenguaje: un conjunto de cadenas. El lenguaje de una máquina es el conjunto de las cadenas que acepta.
• Aceptar / rechazar: la máquina dice sí o no a una cadena.

Estados, transiciones, eventos y acciones

Piensa en un horno microondas. Espera con la puerta cerrada. Presionas Iniciar. El horno enciende el magnetrón y empieza a calentar. En esa historia hay cuatro ideas escondidas, y toda máquina de estados se construye con ellas.

• Estado: una situación estable en la que el sistema espera que algo ocurra (Esperando, Calentando). Resume el pasado: dos historias distintas que terminan en el mismo estado se ven exactamente iguales desde ahí.
• Evento: algo que le ocurre al sistema y que este no controla, como la pulsación de un botón, la llegada de un mensaje o el fin de un temporizador (Iniciar presionado).
• Transición: una flecha de un estado de origen a un estado de destino, marcada con el evento que la dispara.
• Acción: algo que el sistema hace al reaccionar (encender el magnetrón).

                 Iniciar presionado / enciende magnetrón
   (Esperando) ---------------------------------> (Calentando)

En la historia del microondas, el evento es el botón Iniciar y la acción es encender el magnetrón. No los mezcles: el evento viene de afuera, la acción es la respuesta del sistema.

Inicial, terminal, guardas

El estado inicial es donde empieza toda nueva instancia. Un estado terminal (final) es donde termina: ninguna transición sale de él. En la vida de un pedido, cancelled y refunded son terminales, así que después de ellos todo evento debe ser rechazado.

En UML (un lenguaje de dibujo para software) la etiqueta de una transición tiene hasta tres partes, siempre en este orden. La guarda es una prueba de sí o no entre corchetes: la transición solo puede ocurrir si es verdadera.

evento [guarda] / acción
coinInserted [amount >= price] / dispenseItem

Acciones en estados: entrada y salida

Una acción puede estar en la transición o en el estado. Una acción de entrada se ejecuta cada vez que el estado se vuelve activo, y una acción de salida cada vez que se abandona, sea cual sea el camino. Si la luz del pasillo debe encenderse siempre que una puerta automática llega a Abierta, y tres flechas distintas llevan a Abierta, pon "encender la luz" como acción de entrada de Abierta. La escribes una sola vez, y una cuarta flecha creada mañana no puede olvidarla.

La tabla de transiciones

Una máquina se puede escribir como tabla: una fila por estado, una columna por evento. Cada celda guarda el siguiente estado, o - cuando el evento no está permitido ahí. Ejecutar la máquina es simple: mira la celda (estado actual, evento). Si tiene un estado, ve a él. Si está vacía, rechaza el evento y no cambies nada.

Sigue un pedido que empieza en created y recibe pay, ship, deliver, refund: created, paid, shipped, delivered, refunded. Un pedido en paid que recibe deliver encuentra una celda vacía, así que el evento se rechaza. Así la tabla te impide entregar algo que nunca fue enviado.

La tabla es una función parcial sobre los pares (estado, evento). Con 6 estados y 5 eventos hay 6 × 5 = 30 pares. La tabla de arriba define 6 de ellos, así que los otros 24 deben ser rechazados. Una prueba puede recorrer los 30 pares: los 6 válidos deben funcionar, y los 24 restantes deben fallar sin cambiar el estado.

Por qué un solo campo de estado vence a varias banderas

Algunos programas guardan un pedido con una bandera de sí o no por cada hecho: isPaid, isShipped, isDelivered, isCancelled, isRefunded. Cinco banderas se combinan de 2^5 = 32 maneras, pero el negocio conoce solo 6 situaciones. Las otras 26, como "cancelado y entregado", no significan nada, y aun así la base de datos las guarda sin quejarse.

Un solo campo de estado con 6 valores permitidos hace imposible representar las 26 combinaciones sin sentido.

Un ejemplo pequeño: el torniquete

Empieza en Locked y envía coin, push, push, coin, coin, push. Los estados son Locked, Unlocked, Locked, Locked, Unlocked, Unlocked, Locked. El paso de Unlocked a Locked ocurre dos veces, así que pasaron dos personas. Fíjate en dos cosas: la misma entrada (push) hace cosas distintas en estados distintos, y la segunda moneda seguida se pierde, porque esta máquina tiene solo dos estados y no puede contar créditos.

Autómatas finitos deterministas (AFD)

Ahora usamos máquinas de estados para leer palabras. Imagina un juego de mesa en el que pones una ficha en la casilla de inicio y lees una palabra, una letra a la vez. Para cada letra, el tablero te dice exactamente a qué casilla ir. Cuando se acaban las letras, miras dónde está la ficha: en una casilla verde significa "sí, aceptada", en cualquier otra significa "no". Ese tablero es un autómata finito determinista, o AFD (en inglés, DFA).

Un AFD se describe con cinco cosas, la 5-tupla (Q, Σ, δ, q0, F):

Determinista significa que no hay elección. En cada estado, para cada letra, hay exactamente un siguiente estado, y no hay transiciones ε (movimientos que cambian de estado sin leer nada). Así, la ejecución sobre una palabra es un único camino.

Aceptar una palabra

El AFD lee la palabra desde el estado inicial. La palabra es aceptada si el estado alcanzado tras la última letra está en F, y rechazada en caso contrario. El lenguaje del AFD es el conjunto de todas las palabras que acepta. ¿Y la palabra vacía? No tiene letras, así que no se hace ningún movimiento y nos quedamos en el estado inicial. Por lo tanto ε es aceptada si y solo si el estado inicial es de aceptación. Este caso límite vale la pena probarlo en cualquier programa.

Prueba la palabra abab: q0, a lleva a q1, b lleva a q2, a lleva a q1, b lleva a q2. Termina en q2, así que es aceptada. Para descubrir el lenguaje, pregunta qué recuerda cada estado: q0 significa que la palabra no termina ni en a ni en ab, q1 significa que termina en a, q2 significa que termina en ab. Solo q2 acepta, así que este AFD acepta las palabras que terminan en ab, lo mismo que la expresión regular (a|b)*ab.

Más ejemplos

Paridad. Un AFD sobre {0, 1} con dos estados E (par, inicial y de aceptación) y O (impar) que cambia con cada 1 y se queda quieto con cada 0 acepta las palabras con una cantidad par de 1. La palabra 1011011 tiene cinco 1, así que termina en O y es rechazada.

Divisible por 3. Lee un número binario desde el primer bit (el más significativo). Leer un nuevo bit b convierte el valor n en 2n + b, así que el nuevo resto depende solo del resto anterior y de b. Tres restos, tres estados: 0, 1, 2. Desde 0 vas a 0 o 1; desde 1 a 2 o 0; desde 2 a 1 o 2 (leyendo 0 o 1). Inicio y aceptación en el resto 0, lo que también acepta la cadena vacía, contada como 0. La palabra 110 (seis) pasa por 0, 1, 0, 0 y es aceptada; 101 (cinco) pasa por 0, 1, 2, 2 y es rechazada.

El estado muerto y los AFD completos

Los diagramas suelen omitir las flechas que llevan al rechazo seguro. Un AFD completo tiene una flecha para cada estado y cada letra. Para completar uno, agrega un estado muerto (también llamado estado trampa o de error): no es de aceptación y toda letra te mantiene en él. Toda palabra que cae ahí nunca sale.

Ejecutar dos AFD a la vez: el producto

La construcción del producto ejecuta dos AFD en paralelo. Cada nuevo estado es un par (estado de A, estado de B), y cada letra mueve ambas partes. Para la intersección (palabras aceptadas por los dos) un par acepta cuando ambas partes aceptan. Para la unión un par acepta cuando al menos una parte acepta. Dos AFD de 2 estados cada uno dan hasta 2 × 2 = 4 estados-par. Por ejemplo, A (cantidad par de a) y B (termina en b) dan los cuatro pares (par, no b), (impar, no b), (par, b) e (impar, b); para la intersección solo (par, b) acepta, así que exactamente uno de los 4 estados acepta.

Por qué los AFD son rápidos

// table[state][symbol] da el siguiente estado
let state = start;
for (const symbol of input) {
	state = table[state][symbol];
}
return accepting.has(state);

Una cadena de n letras cuesta n consultas: tiempo lineal, memoria constante. El costo de un AFD se paga antes, cuando se construye la tabla. Por eso los lexers (la parte del compilador que corta el texto en palabras) son AFD guiados por tabla.

Autómatas no deterministas y construcción de subconjuntos

¿Y si la máquina pudiera adivinar? Imagina que llegas a una bifurcación en un laberinto y, por arte de magia, haces una copia de ti mismo por cada camino. Todas las copias caminan al mismo tiempo. Si cualquier copia llega al tesoro, ganas. Eso es un autómata finito no determinista, o AFN (en inglés, NFA).

Un AFN hace dos cosas que un AFD no puede. Primero, su función de transición devuelve un conjunto de estados: posiblemente vacío, posiblemente con varios elementos. Segundo, puede tener transiciones ε, que se mueven sin leer letra.

La aceptación es existencial: una palabra es aceptada si existe alguna secuencia de elecciones que lee toda la palabra y termina en un estado de aceptación. No importa que otros caminos fallen.

De AFN a AFD: construcción de subconjuntos

El truco: en vez de seguir muchas copias, guarda el conjunto de todos los estados en los que el AFN podría estar. Ese conjunto se vuelve un estado del AFD. Necesitamos dos auxiliares:

• ε-clausura(s) (ε-closure): todos los estados que se alcanzan desde s sin leer nada. Contiene al propio s y todo lo que se alcanza por cadenas de flechas ε.
• move(T, a): todos los estados alcanzados desde los estados del conjunto T leyendo la letra a.

1. El estado inicial del AFD es la ε-clausura del estado inicial del AFN.
2. Para cada estado T del AFD y cada letra a, el siguiente estado es ε-clausura(move(T, a)).
3. Repite para cada nuevo conjunto que aparezca, hasta que no aparezca ninguno nuevo.
4. Un conjunto es de aceptación si contiene al menos un estado de aceptación del AFN (su intersección con F no es vacía).

Desde el estado 0 las flechas ε traen 1 y 3, y ninguno de los dos tiene flechas ε, así que la clausura de 0 es {0, 1, 3}: el estado inicial T del AFD. Con a: move(T, a) = {2}, y la clausura de {2} es {2, 3}. Con b: move(T, b) = {4}, y la clausura de {4} es {1, 4}.

Un segundo ejemplo, simple, sin ε. El AFN tiene q0 (inicial), q1, q2 (de aceptación), con q0 en a yendo a {q0, q1}, q0 en b a {q0}, q1 en b a {q2}. Desde {q0}: a lleva a {q0, q1}, b se queda en {q0}. Desde {q0, q1}: a se queda, b lleva a {q0, q2}. Desde {q0, q2}: a lleva a {q0, q1}, b lleva a {q0}. Aparecen solo 3 conjuntos, y solo {q0, q2} contiene a q2, así que solo él acepta. El lenguaje es el de las palabras que terminan en ab.

El precio: el tamaño puede explotar

Un conjunto de m estados se puede elegir de hasta 2^m maneras, así que un AFD puede necesitar exponencialmente más estados. El caso clásico es "el n-ésimo símbolo desde el final es a". El AFN se queda en bucle en el estado inicial y adivina cuándo salir, usando n + 1 estados. Un AFD debe recordar una ventana con las últimas n letras, así que necesita 2^n estados.

Simular en vez de convertir

También puedes ejecutar el AFN directamente, guardando el conjunto de estados actuales. Para una palabra de n letras y un AFN de tamaño m (estados más transiciones) esto cuesta tiempo O(n · m) y solo memoria O(m). Convertir antes a AFD puede generar hasta 2^m estados, pero después cada palabra cuesta solo O(n). Las herramientas de búsqueda suelen simular el AFN (o construir los estados del AFD bajo demanda y guardarlos en caché); los generadores de lexers pagan la conversión una sola vez.

Lenguajes regulares y expresiones regulares

Cuando buscas "c?t" en un documento o escribes *.png para listar imágenes, describes un patrón en vez de una palabra. Una expresión regular (regex) es una forma corta de describir un conjunto entero de palabras. Los conjuntos que las regex describen son los lenguajes regulares, y son exactamente los lenguajes que los autómatas finitos reconocen.

Los tres bloques básicos

Además de esas tres, una regex usa símbolos simples y ε. Fíjate en que a* contiene ε (cero repeticiones), luego a, aa, y así sucesivamente: un lenguaje infinito cuyas palabras son todas finitas. Otros signos son atajos que se pueden reescribir con las tres: r+ = rr* (una o más), r? = r|ε (opcional) y [abc] = a|b|c (una clase). Dan comodidad, no poder.

La precedencia funciona como en la aritmética, de la más fuerte a la más débil: clausura (como una potencia), luego concatenación (como multiplicación), luego unión (como suma). Así ab|c* significa "la palabra ab, o cualquier cantidad de c", y no a, luego b o c, repetido.

Leer expresiones

• (a|b)*abb: cualquier palabra de a y b (incluso vacía) seguida de abb. Entonces la palabra debe terminar en abb. babb coincide; bba, bab, ab y bbb no.
• (a|b)*a(a|b): el penúltimo símbolo es a. De longitud 3: aaa, aab, baa, bab (4 palabras); aba, abb, bba y bbb quedan fuera.
• b*(ab*ab*)*: una cantidad par de a. Piensa en el autómata de dos estados (par, impar): volver a par exige dos a, con cualquier cantidad de b en medio.

Teorema de Kleene: expresiones y autómatas son gemelos

Las expresiones regulares describen lenguajes y los autómatas finitos los reconocen. El teorema de Kleene dice que tienen el mismo poder. Por eso un generador de lexers puede tomar tus regex y producir un autómata por ti. El camino de la regex al autómata es la construcción de McNaughton-Yamada-Thompson, que arma un AFN pieza por pieza:

• Un símbolo se vuelve un fragmento de 2 estados (uno inicial y uno de aceptación).
• La unión agrega 2 estados nuevos (nuevo inicial, nuevo de aceptación) unidos a los fragmentos por 4 flechas ε. Así a|b tiene 2 + 2 + 2 = 6 estados.
• La clausura (estrella) también agrega 2 estados y flechas ε para repetir y para saltar.
• La concatenación no agrega estados nuevos: pega el final de un fragmento con el inicio del siguiente.

Cada fragmento tiene un estado inicial y uno de aceptación, así que las piezas encajan como bloques de Lego. El AFN tiene como máximo cerca del doble del tamaño de la expresión, así que la construcción es lineal.

Qué se puede hacer con lenguajes regulares

Los lenguajes regulares son cerrados bajo unión, concatenación, estrella, complemento e intersección: aplicar esas operaciones a lenguajes regulares da un lenguaje regular. Cada una tiene una construcción detrás, como el producto para la intersección o el intercambio en un AFD completo para el complemento.

Lo que no pueden hacer

Un autómata finito solo tiene sus estados como memoria. Toma el lenguaje a^n b^n (algunas a seguidas del mismo número de b). Tras leer las a, la máquina tendría que recordar exactamente cuántas fueron, y hay infinitas posibilidades. Con k estados, entre los prefijos a^0, a^1, ..., a^k dos deben caer en el mismo estado (el principio del palomar: más palomas que nidos). Completa ambos con las mismas b y el autómata acepta los dos o rechaza los dos, así que se equivoca en uno. Esa es la idea del lema del bombeo. Por lo tanto a^n b^n no es regular.

Minimización de autómatas

Imagina dos niños en la clase que siempre dan la misma respuesta a toda pregunta que les haces, ahora y en el futuro. Podrías quedarte con uno solo y nada cambiaría. En un AFD, dos estados así se llaman equivalentes, y la minimización los junta para dejar la máquina lo más pequeña posible.

Muchos AFD distintos reconocen el mismo lenguaje, pero solo uno tiene el menor número de estados, salvo por el nombre de los estados. Ese es el AFD mínimo. Como es único, da una prueba: dos AFD son equivalentes exactamente cuando sus formas mínimas son iguales.

¿Distinguibles o equivalentes?

Dos estados p y q son distinguibles si existe una cadena w tal que leer w desde p termina en aceptación y desde q no (o al revés). Si ninguna cadena los distingue, son equivalentes y pueden volverse un solo estado. La cadena vacía por sí sola ya separa los estados de aceptación de los de no aceptación.

La equivalencia es recursiva: p y q son equivalentes si coinciden en la aceptación y, para cada letra, sus destinos son equivalentes. Así, dos estados de aceptación con δ(p, a) = r y δ(q, a) = s, siendo r y s distintos, aún pueden ser equivalentes, cuando r y s sean equivalentes entre sí. Comparar las filas de la tabla no basta; por eso el algoritmo trabaja con grupos.

Refinamiento de particiones

1. Empieza con la partición inicial de dos grupos: los estados de aceptación y los de no aceptación.
2. Para cada grupo y cada letra, mira a qué grupo va cada estado. Si los estados de un grupo van a grupos distintos, divídelo en consecuencia.
3. Repite hasta que ningún grupo se divida. Cada grupo final se vuelve un estado del AFD mínimo.

Partición inicial: A = {S0, S1} y B = {S2, S3}. Con 0: S0 y S1 van a S1 y S0, ambos en A; S2 y S3 van a S3 y S2, ambos en B. Con 1: S0 y S1 van a S2 y S3, ambos en B; S2 y S3 van a S0 y S1, ambos en A. Ningún grupo se divide, así que el AFD mínimo tiene 2 estados. Acepta las palabras con una cantidad par de 1.

Otra ejecución. Estados A, B, C, D, E con D de aceptación, y partición inicial {A, B, C, E} y {D}. Con b, A y C van a C (dentro del grupo) mientras B y E van a D (fuera). El grupo se divide en {A, C} y {B, E}. Probando de nuevo, nada más se divide, así que el AFD mínimo tiene 3 estados.

ronda 0:  { A B C E }    { D }
                |
           (con b: A,C -> dentro, B,E -> D)
                v
ronda 1:  { A C }  { B E }  { D }   sin más divisiones
          = 3 estados

Contar estados por lo que hay que recordar

El teorema de Myhill-Nerode dice que el número de estados del AFD mínimo es igual al número de clases de prefijos que necesitan futuros distintos. Ejemplo: las palabras que contienen aab como subcadena. Necesitamos q0 (sin progreso), q1 (termina en a), q2 (termina en aa), q3 (ya contiene aab: de aceptación, y se queda ahí para siempre). El final b separa aa de a y de ε; ab separa a de ε; y la cadena vacía separa aab del resto. Así el AFD mínimo completo tiene 4 estados.

Cuando los estados producen respuestas

El algoritmo clásico solo conserva la pregunta "¿aceptada o no?". Un lexer necesita más: qué token se reconoció, como IF frente a ID. La solución es empezar de una partición más fina: un grupo por cada tipo de salida (cada token) más el grupo de no aceptación. El resto corre como siempre. La misma idea vale para cualquier máquina cuyos estados produzcan salidas distintas.

Máquinas de Mealy y de Moore

Hasta ahora las máquinas solo decían sí o no. Muchas veces queremos que respondan con algo, como un semáforo que muestra un color, o un circuito que enciende una lámpara. Las máquinas con salida vienen en dos sabores.

¿Por qué n + 1 en Moore? Una entrada de n símbolos causa n transiciones, así que la máquina visita n + 1 estados, y cada estado visitado tiene una salida, incluido el primero, que no depende de ninguna entrada. Con 5 símbolos de entrada una máquina de Moore produce 6 salidas y una de Mealy produce 5.

Ejemplo: detectar dos 1 seguidos

S1 significa "el último símbolo fue 1". La salida es 1 cuando el símbolo actual y el anterior son ambos 1. Para la entrada 0110111: (S0,0) da 0; (S0,1) da 0; (S1,1) da 1; (S1,0) da 0; (S0,1) da 0; (S1,1) da 1; (S1,1) da 1. Salida: 0010011.

De Mealy a Moore

Para convertir, mueve la salida de cada transición al estado de destino. Si a un estado se llega con transiciones de salidas distintas, divídelo, una copia por cada salida. Aquí a S1 se llega con salida 0 (el primer 1) y con salida 1 (los 1 siguientes), así que S1 se vuelve dos estados. La máquina de Moore tiene 3 estados. Una máquina de Moore puede necesitar más estados que la de Mealy, y nunca menos.

Máquinas en hardware

Un circuito combinacional tiene una salida que depende solo de las entradas actuales, como el botón de una calculadora. Un circuito secuencial tiene realimentación y memoria, así que su salida también depende del estado, que resume las entradas pasadas. Los elementos de memoria son latches y flip-flops. Todo circuito secuencial síncrono (guiado por un reloj) es una máquina de estados finita: los flip-flops guardan el estado y la lógica combinacional calcula el siguiente estado y la salida.

Con codificación binaria (el menor número de bits) necesitas ⌈log2(número de estados)⌉ flip-flops. Para 6 estados, log2(6) es cerca de 2,58, redondeado hacia arriba da 3 flip-flops. Tres bits dan 8 códigos, de los cuales 6 se usan. Los 2 códigos sobrantes deben tratarse en el diseño para que la máquina no quede atrapada en ellos.

Statecharts: jerarquía, guardas, estados paralelos

Un reproductor de música tiene un estado Reproduciendo y un estado Pausado. También tiene "apagar", que debe funcionar en ambos. En un diagrama plano dibujas una flecha apagar saliendo de cada estado. Con diez estados, diez flechas. Los statecharts, inventados por David Harel, resuelven esto con tres ideas: jerarquía, guardas y regiones paralelas.

Jerarquía: superestados

Agrupa Reproduciendo y Pausado dentro de un superestado llamado Encendido, y dibuja la flecha powerOff una sola vez, saliendo de Encendido. Los subestados la heredan. Cuando llega un evento, la máquina busca primero una transición en el subestado activo. Si no hay, la búsqueda sube al superestado.

+--------------- Encendido --------------+
|  inicial: Reproduciendo                |
|   (Reproduciendo) --pause--> (Pausado) |   powerOff
|   (Reproduciendo) <--play--  (Pausado) |-------------> (Off)
+----------------------------------------+

Si el reproductor está en Pausado y recibe powerOff, Pausado no tiene esa flecha, así que la búsqueda sube hasta Encendido, que lleva a Off. Un statechart jerárquico siempre puede aplanarse en una máquina común, pero más grande y más difícil de leer.

Guardas

Una guarda permite que un mismo evento lleve a destinos distintos según los datos: withdraw [balance >= amount] y withdraw [balance < amount]. Como vimos, las guardas del mismo evento en el mismo estado deben ser mutuamente excluyentes.

Transiciones internas y externas

Supón que Calentando tiene la acción de entrada startTimer y la acción de salida stopTimer. Una transición de Calentando a sí mismo en cada tick puede modelarse de dos maneras:

• Autotransición externa: sale del estado y vuelve a entrar. Ejecuta la acción de salida y luego la de entrada: el temporizador se detiene y se inicia en cada tick.
• Transición interna: nunca cruza el borde del estado. Ejecuta solo su propia acción. Si solo quieres contar el tick sin reiniciar el temporizador, este es el modelo correcto.

Historia: recordar dónde estabas

El reproductor está en Pausado (dentro de Encendido) cuando una llamada telefónica lo lleva al estado Llamada, fuera de Encendido. Cuando la llamada termina, quieres volver a Pausado, no al inicio. Un pseudoestado de historia da esta memoria al superestado. La historia superficial (H) recuerda solo el nivel justo debajo. La **historia profunda (H*)** recuerda toda la configuración anidada. En la primera entrada, cuando aún no hay historia, se usa el subestado inicial (Reproduciendo).

Orden de las acciones al cruzar niveles

Cuando una transición va de A1 (dentro de A) a B1 (dentro de B) con acción t, el orden es como cerrar y abrir cajas:

1. acciones de salida de los estados que se abandonan, del más interno al más externo: sale de A1, luego sale de A;
2. la acción de la transición: t;
3. acciones de entrada de los estados que se activan, del más externo al más interno: entra en B, luego entra en B1.

Un superestado se activa antes que sus subestados y se desactiva después de ellos.

Regiones paralelas (ortogonales)

Un reproductor tiene un modo de reproducción (Reproduciendo, Pausado, Detenido) y un volumen (Normal, Silenciado). Son independientes. Un diagrama plano necesita un estado por cada combinación. Un estado compuesto con regiones ortogonales da a cada aspecto su propio diagrama pequeño, y el estado del sistema es el conjunto de subestados activos, uno por región.

Regiones con k1, k2, ..., kn subestados equivalen a k1 × k2 × ... × kn estados planos. El dibujo crece como una suma, la máquina plana como un producto. Esa es la explosión de estados que la notación evita.

Autómatas de pila y gramáticas libres de contexto

Un autómata finito no puede comprobar que los paréntesis coincidan: ((())) está bien y (() no. Tendría que contar los paréntesis abiertos sin límite. Dale a la máquina una pila, un montón de platos en el que solo tocas el plato de arriba (el último en entrar es el primero en salir), y puede. Un autómata de pila (AP) es un autómata finito más una pila. Cada transición mira el estado, el símbolo de entrada y el tope de la pila, y puede apilar o desapilar.

Contar con una pila: a^n b^n

Para aceptar n letras a seguidas de n letras b: apila una X por cada a, desapila una X por cada b, y acepta si la entrada termina con la pila vacía.

lee a  [X]
lee a  [X X]
lee b  [X]
lee b  [ ]
lee b  pila vacía, sin movimiento -> RECHAZA

Una X sobrante significa demasiadas a; una X faltante significa demasiadas b. La aceptación exige las dos cosas: fin de la entrada y pila vacía.

Gramáticas: reglas que construyen palabras

Una gramática libre de contexto (GLC) tiene terminales (los símbolos de verdad), no terminales (nombres de tipos de frase), un símbolo inicial y producciones A → α, donde el lado izquierdo es un único no terminal y α es cualquier secuencia de símbolos. "Libre de contexto" significa que la regla para A vale donde sea que aparezca A, sin importar lo que lo rodee. La sintaxis de los lenguajes de programación se escribe así.

S -> a S b | ε
S => aSb => aaSbb => aaaSbbb => aaabbb

Cada uso de S → aSb agrega una a a la izquierda y una b a la derecha, y S → ε termina el proceso. La gramática S → (S)S | ε genera los paréntesis balanceados. Los dos lenguajes son libres de contexto pero no regulares. El anidamiento sin límite es la marca de esa diferencia. Por eso el lexer (regular) no puede comprobar paréntesis, y ese trabajo es del parser (libre de contexto).

Ambigüedad

Una gramática es ambigua si alguna cadena tiene más de un árbol de derivación (un árbol que muestra cómo la construyeron las reglas). Con E → E + E | E * E | id, la cadena id + id * id tiene 2 árboles: uno con + en la raíz, otro con * en la raíz. Con números, 2 + 3 * 4 sería 14 en un árbol y 20 en el otro. El arreglo habitual es estratificar la gramática en niveles (expresión, término, factor), incorporando en ella precedencia y asociatividad.

¿Adivinar ayuda aquí?

En los autómatas finitos, adivinar (no determinismo) no añadió poder. En los autómatas de pila sí: los lenguajes libres de contexto deterministas son un subconjunto propio de los libres de contexto. El lenguaje de las palabras seguidas de su espejo, w w^R, necesita adivinar dónde está el medio. Con un marcador c en el medio, w c w^R, no hace falta adivinar, y es determinista. En la práctica, los parsers rápidos como LL y LR son autómatas de pila deterministas, y por eso las gramáticas de los lenguajes de programación se diseñan para caber en esa clase.

Dónde una pila no basta

Una pila puede comprobar una dependencia anidada a la vez. En a^n b^n c^n hay dos igualdades a la vez (a con b, y b con c), y la primera comparación vacía la pila. Así a^n b^n c^n no es libre de contexto (la prueba usa el lema del bombeo para lenguajes libres de contexto). Curiosamente, a^n b^n c^m y a^m b^n c^n son ambos libres de contexto, pero su intersección es a^n b^n c^n. Por lo tanto los lenguajes libres de contexto no son cerrados bajo intersección.

Máquinas de Turing y computabilidad

Imagina una tira de papel muy larga con cuadritos, un lápiz con goma y una persona que sigue un pequeño libro de reglas. La persona mira un cuadrito y sigue una regla: escribir un símbolo, moverse a la izquierda o a la derecha y pasar a otra página del libro. Eso es una máquina de Turing, inventada por Alan Turing en 1936.

Tiene un control finito (los estados), una cinta ilimitada de celdas y un cabezal. En cada paso lee el símbolo bajo el cabezal y, según el estado, escribe un símbolo, se mueve a la izquierda o a la derecha y cambia de estado. Poder volver atrás y reescribir es lo que la hace más potente que un autómata de pila, cuya pila solo se alcanza por arriba.

Un programa pequeño: sumar 1 en binario

empieza en q0, cabezal en el bit más a la derecha
(q0, 1) -> escribe 0, mueve a la izquierda, sigue en q0
(q0, 0) -> escribe 1, se queda, va a halt
(q0, _) -> escribe 1, se queda, va a halt
(_ = celda en blanco)

Con la cinta 1011 (once) y el cabezal en el último 1: escribe 0 y se mueve a la izquierda (1010), escribe 0 y se mueve a la izquierda (1000), luego llega a un 0, escribe 1 y se detiene: 1100, que es doce. El acarreo viajó hacia la izquierda, como cuando sumas a mano.

Tres grandes ideas

• Tesis de Church-Turing: varios modelos inventados de forma independiente (máquinas de Turing, cálculo lambda, funciones recursivas) resultaron ser equivalentes. La tesis dice que esa clase es exactamente lo que entendemos por "computable". Así que lo que una máquina de Turing no puede hacer, ningún lenguaje de programación puede.
• Máquina de Turing universal: una máquina que lee de la cinta la tabla de transiciones de cualquier otra máquina y la ejecuta. Es la teoría detrás de la computadora de propósito general y de todo intérprete. También nos permite hablar de programas que reciben programas como entrada.
• Turing-completo: un modelo que puede simular cualquier máquina de Turing. Necesita memoria ilimitada y decisión más repetición sin un límite fijado de antemano. Los autómatas finitos y los autómatas con una sola pila no son Turing-completos.

Decidible y reconocible

Un lenguaje es decidible si una máquina de Turing siempre se detiene y responde sí o no. Es reconocible (semidecidible) si una máquina se detiene y acepta toda palabra del lenguaje, pero puede correr para siempre con las demás. Decidible es un subconjunto propio de reconocible. Una regla útil: un lenguaje es decidible exactamente cuando él y su complemento son ambos reconocibles.

El problema de la parada

Pregunta: dado un programa y una entrada, ¿termina o corre para siempre? Turing demostró que ningún algoritmo responde correctamente en todos los casos: el problema de la parada es indecidible. Es reconocible (ejecuta el programa; si se detiene, di que sí) pero no decidible (nunca puedes estar seguro de que una ejecución larga no se detendrá más tarde). Aquí está la idea de la prueba, por diagonalización:

# Supón que H(p, x) siempre se detiene y dice si p se detiene con la entrada x
def D(p):
    if H(p, p):
        while True:
            pass        # bucle infinito
    else:
        return          # se detiene
# ¿Qué hace D(D)?

Si H dice que D(D) se detiene, entonces D(D) entra en bucle, y H se equivocó. Si H dice que D(D) entra en bucle, entonces D(D) se detiene, y H se equivocó otra vez. Por lo tanto H no puede existir. D usa H solo como subrutina, así que ninguna implementación ingeniosa escapa.

El teorema de Rice generaliza esto: ningún algoritmo decide, para todo programa, una propiedad no trivial de lo que el programa computa (por ejemplo, "¿esta función puede alguna vez devolver null?"). Por eso los verificadores de tipos, los analizadores y los optimizadores son conservadores y se equivocan hacia el lado seguro: un optimizador aplica un cambio solo cuando puede probar que es seguro, y un verificador de tipos rechaza algunos programas correctos.

La jerarquía de Chomsky

Cada clase contiene a la que está encima en la tabla. Tener menos poder tiene una ventaja: preguntas como "¿esta máquina acepta alguna palabra?" o "¿estas dos máquinas son equivalentes?" son decidibles para autómatas finitos, pero indecidibles para modelos Turing-completos.

Máquinas de estados en software: patrón State, protocolos, flujos de trabajo

De vuelta a la programación de todos los días. Siempre que una cosa tiene una vida con etapas (un pedido, una descarga, un inicio de sesión, una conexión), una máquina de estados ayuda a decir exactamente qué puede pasar y cuándo.

Dos formas de programarla

• Patrón State (orientado a objetos): el comportamiento de cada estado vive en su propia clase, con la misma interfaz. El objeto de contexto delega en el objeto del estado actual, y así parece cambiar de clase cuando cambia el estado. Ventaja: todo lo de un estado queda en un solo lugar. Costo: la visión general de las transiciones queda repartida en varias clases.
• Guiada por tabla: las transiciones son datos, una tabla que asigna (estado, evento) al siguiente estado, y una función genérica hace la consulta. Ventaja: agregar una transición es agregar una fila, sin tocar el mecanismo, y un programa puede leer la tabla para generar pruebas y diagramas.

Protocolos

Un protocolo es un conjunto de reglas sobre quién puede decir qué y cuándo. El "cuándo" es exactamente lo que representa un estado. Por eso los protocolos de comunicación, como el establecimiento de una conexión TCP, se especifican como máquinas de estados: queda explícito qué hacer con cada mensaje en cada fase, incluidos los mensajes inesperados, fuente frecuente de fallos.

Flujos de trabajo: el ejemplo del pedido

• Guarda el estado en un solo campo con un conjunto cerrado de valores (y no derivado de paidAt, shippedAt, cancelledAt, lo que permite combinaciones sin sentido).
• Una función de transición recibe el estado y el evento. Si el evento no está permitido, rechaza de forma explícita (un tipo de resultado o una excepción) y no tiene ningún efecto sobre el estado. Quien llama decide qué hacer con el error.
• Genera las pruebas a partir de la tabla: para cada par (estado, evento), espera éxito si el par está en la tabla y rechazo si no. Ahora agrega un estado returned, un evento return y una transición desde delivered. Los pares pasan de 6 × 5 = 30 a 7 × 6 = 42, y los rechazos de 30 − 6 = 24 a 42 − 7 = 35. Los 11 nuevos casos negativos quedan probados sin que nadie los escriba.
• Genera el diagrama a partir de la tabla y mantén una prueba que falle cuando el diagrama versionado difiera de lo que genera la tabla. Un diagrama dibujado a mano es una segunda copia de las reglas, y las copias se alejan. Con una única fuente de verdad más la prueba de actualidad, eso no ocurre.

Deja que el compilador te revise

type OrderState = "created" | "paid" | "shipped";

function assertNever(value: never): never {
	throw new Error(`unexpected state: ${String(value)}`);
}

function label(state: OrderState): string {
	switch (state) {
		case "created": return "Created";
		case "paid": return "Paid";
		case "shipped": return "Shipped";
		default: return assertNever(state);
	}
}

Tras tratar todos los casos, el tipo que queda para state es never. Si alguien agrega "delivered" al tipo y olvida el switch, lo que queda deja de ser never, y pasarlo a assertNever es un error de compilación. El compilador lista todos los lugares que necesitan actualización.

def transition(:created, :pay), do: {:ok, :paid}
def transition(:created, :cancel), do: {:ok, :cancelled}
def transition(:paid, :ship), do: {:ok, :shipped}
def transition(:shipped, :deliver), do: {:ok, :delivered}
def transition(_state, _event), do: {:error, :invalid_transition}

Las cláusulas se prueban de arriba hacia abajo. La última, genérica, atrapa todos los demás pares, así que transition(:shipped, :pay) devuelve {:error, :invalid_transition}. El orden importa: si la cláusula genérica fuera primero, coincidiría con todo.

La vida real no es una función pura

Concurrencia. Dos solicitudes leen status = 'created'; una quiere pagar, la otra cancelar. Una transición es leer, comprobar, escribir, y si esos pasos no son atómicos las dos pueden partir del mismo estado. Haz que la comprobación sea parte de la escritura, una actualización condicional (compare-and-swap). Opciones equivalentes: bloquear la fila con SELECT ... FOR UPDATE, o usar una columna de versión (control optimista).

UPDATE orders SET status = 'paid'
WHERE id = 42 AND status = 'created';
-- 1 fila cambiada: ganamos. 0 filas: otro se movió primero.

Duplicados. Las colas suelen entregar un mensaje al menos una vez, así que el evento pay puede llegar dos veces. Una tabla estricta ayuda: la segunda copia encuentra el pedido en paid, donde pay no está permitido, y es rechazada. Aun así debes decidir la política a propósito: tratar el rechazo como error, o reconocer el duplicado y confirmarlo sin efecto.

Efectos externos. En pay el servicio cobra una tarjeta y luego guarda paid. Si el proceso se cae después del cobro y antes de guardar, el evento se procesa de nuevo con el pedido todavía en created. Los dos pasos no pueden ser atómicos entre sí, así que el reprocesamiento debe ser seguro. El remedio estándar es hacer el efecto idempotente (idempotente), por ejemplo con una clave de idempotencia enviada al proveedor de pagos. La máquina de estados te protege después de guardar; la idempotencia te protege en la ventana anterior.

Juntándolo todo

Subiste toda la escalera. Esta tabla pone las máquinas lado a lado.

Errores que evitar

• Intercambiar los estados de aceptación para obtener el complemento de un AFD que no es completo.
• Olvidar que ε se acepta exactamente cuando el estado inicial es de aceptación.
• Creer que un AFN reconoce lenguajes que un AFD no reconoce. No los reconoce; solo puede ser más pequeño.
• Olvidar ε al leer a*.
• Contar n salidas para una máquina de Moore. Son n + 1.
• Usar dos guardas que se solapan para el mismo evento.
• Creer que un lexer comprueba paréntesis balanceados. Eso exige una pila.
• Tratar un evento rechazado como un cambio de estado. El rechazo no cambia nada.