Los límites: por qué una FSM no puede contar

Hay una frase que se repite sin explicarse: una máquina de estados finita no puede contar. Suena a limitación menor, casi anecdótica, hasta que uno se da cuenta de cuántas cosas cotidianas son contar disfrazado —emparejar paréntesis, validar anidamiento, comprobar que hay tantos cierres como aperturas—. La imposibilidad es real, es demostrable en cinco líneas y no depende de la astucia de quien diseñe la máquina. Y lo interesante no es la prohibición en sí, sino lo que revela: el mismo argumento que impide contar es el que garantiza que la máquina se ejecute en memoria constante. Es el mismo hecho visto desde sus dos caras, y entender esa dualidad es lo que permite decidir con criterio cuándo salir del modelo.

El palomar dentro de un camino

Toma un DFA con p estados y dale de comer una cadena de longitud al menos p. Al procesarla, la máquina visita p + 1 estados contando el inicial —uno antes de cada símbolo y uno al final—. Como solo dispone de p estados distintos, por el principio del palomar dos de esas visitas tienen que caer en el mismo estado. No hay forma de evitarlo: no es un defecto de la máquina concreta, es aritmética.

Ese hecho, tan modesto, tiene una consecuencia devastadora. El tramo de cadena consumido entre las dos visitas al mismo estado forma un ciclo en el grafo de transiciones. Y un ciclo se puede recorrer las veces que uno quiera: cero, una, siete. La máquina, al terminar, acaba exactamente en el mismo sitio en los tres casos, porque su única memoria es el estado actual y el estado actual no distingue cuántas vueltas se dieron. Si la cadena original era aceptada, todas las variantes con el ciclo repetido también lo son.

stateDiagram-v2
[*] --> A
A --> B : prefijo x
B --> B : bucle y
B --> C : sufijo z
C --> [*]
note right of B : aqui se repite el estado

Aquí está todo el argumento dibujado. Si la cadena aceptada se descompone en un prefijo x que lleva de A a B, un tramo y que sale de B y vuelve a B, y un sufijo z que lleva de B a un estado aceptador, entonces x z, x y z, x y y z y en general x y^i z acaban todas en el mismo estado aceptador. La máquina no puede distinguirlas porque, literalmente, no tiene dónde guardar la diferencia.

El lema del bombeo, enunciado y usado

Formalizado, lo anterior es el lema del bombeo para lenguajes regulares. Si L es regular, existe una longitud p —la longitud de bombeo, típicamente el número de estados del autómata— tal que toda cadena w de L con longitud al menos p admite una descomposición w = x y z que cumple tres condiciones: el tramo y no es vacío, la longitud de x y no supera p, y para todo i mayor o igual que cero la cadena x y^i z sigue perteneciendo a L.

Las dos primeras condiciones no son adorno. Que y no sea vacío garantiza que bombear cambia realmente la cadena; sin ella el lema sería trivialmente cierto y no serviría para nada. Que x y quepa en las primeras p posiciones garantiza que el ciclo se encuentra dentro del prefijo que forzó la repetición, y es justo esa acotación la que convierte el lema en una herramienta utilizable, porque restringe drásticamente dónde puede estar el tramo bombeable.

El uso estándar es por contradicción, y conviene fijar el orden de los cuantificadores porque es donde todo el mundo se equivoca. El lema no dice que exista alguna cadena bombeable: dice que si el lenguaje es regular, entonces toda cadena larga lo es. Para refutar la regularidad basta con exhibir una sola cadena larga que no admita ninguna descomposición válida. Tú eliges la cadena; el adversario elige la descomposición dentro de las restricciones; tú eliges el i que rompe la pertenencia.

Aplíquémoslo al caso canónico: el lenguaje de las cadenas formadas por n símbolos a seguidos de n símbolos b. Supón que es regular con longitud de bombeo p y toma la cadena con p símbolos a y p símbolos b. Como la longitud de x y no supera p, el tramo y está compuesto exclusivamente por símbolos a y contiene al menos uno. Bombea con i igual a dos: la cadena resultante tiene más símbolos a que b y por tanto no pertenece al lenguaje. Contradicción. El lenguaje no es regular, y con él caen los paréntesis balanceados, los palíndromos y el anidamiento de cualquier profundidad.

Fíjate en dónde hizo el trabajo cada condición del lema. La acotación de la longitud de x y es la que forzó a que el tramo bombeable fuera todo de símbolos a; sin ella, el adversario habría podido elegir un y a caballo entre las dos mitades o compuesto de ambos símbolos, y el argumento se habría complicado sin necesidad. Y que y no sea vacío es lo que garantizó que bombear con i igual a dos produjera realmente una cadena distinta. Elegir bien la cadena de partida es el noventa por ciento del ejercicio: una elección afortunada deja al adversario sin descomposiciones interesantes, y una mala obliga a estudiar casos.

El mismo esquema demuestra que no son regulares el lenguaje de los palíndromos, el de las cadenas con igual número de aperturas y cierres a cualquier profundidad, y el de las cadenas de la forma ww. En los tres, lo que falla es idéntico: hay que recordar una cantidad de información que crece con la entrada. La forma del argumento cambia poco; lo que cambia es la cadena que se elige y el valor de i que rompe la pertenencia.

Myhill y Nerode: la caracterización exacta

El lema del bombeo es una consecuencia de la regularidad; el teorema de Myhill y Nerode es la regularidad misma, dicha de otro modo. Su idea es cambiar el foco de las máquinas a los prefijos. Dos cadenas u y v se consideran indistinguibles respecto de un lenguaje L si, para cualquier sufijo s que se les añada, o bien ambas concatenaciones pertenecen a L o bien ninguna. Es decir, si ningún futuro posible las separa.

Esa relación es de equivalencia y particiona Σ* en clases. El teorema afirma que L es regular si y solo si el número de clases es finito, y que en ese caso el DFA mínimo tiene exactamente una clase por estado. La lectura es preciosa: un estado no es más que un conjunto de historias que el futuro ya no puede distinguir, y la cantidad de estados necesarios es una propiedad del lenguaje, no del ingenio del diseñador.

La relación se calcula en la práctica sin abstracción alguna: dos prefijos son distinguibles si existe un sufijo que los separa, y el contraejemplo suele encontrarse a mano en segundos.

// Dos prefijos son distinguibles si algun sufijo los separa respecto de L.
const distinguibles = (L: (w: string) => boolean, u: string, v: string, sufijos: string[]) =>
  sufijos.some((s) => L(u + s) !== L(v + s))

// L = a^n b^n. Los prefijos "a", "aa", "aaa"... son distinguibles dos a dos:
// el sufijo b^i completa uno hasta L y al otro no. Infinitas clases, no regular.
const balanceado = (w: string) => /^(a*)(b*)$/.test(w) &&
  w.replace(/b/g, "").length === w.replace(/a/g, "").length

distinguibles(balanceado, "a", "aa", ["b", "bb", "bbb"])   // true

Con esta herramienta la no regularidad de las cadenas balanceadas se ve de un vistazo y sin contradicciones. Los prefijos formados por i símbolos a son distinguibles dos a dos: para separar el de i del de j basta el sufijo con i símbolos b, que completa uno hasta una cadena del lenguaje y al otro no. Como hay infinitos prefijos mutuamente distinguibles, hay infinitas clases, y por tanto ningún autómata finito. La demostración es directa, no por reducción al absurdo, y además cuantifica el problema: no es que falten estados, es que harían falta infinitos.

Lo que hace falta entonces: la pila y el context

Si contar exige memoria no acotada, la salida es añadirla, y la teoría ofrece el peldaño inmediatamente superior: el autómata con pila. Es el mismo control finito de siempre más una pila de longitud ilimitada sobre la que se apila y desapila en cada transición. Con esa única adición, las cadenas balanceadas se reconocen sin esfuerzo —apila por cada apertura, desapila por cada cierre, acepta si la pila queda vacía— y la clase reconocida pasa a ser la de los lenguajes libres de contexto, el tipo 2 de Chomsky. Es exactamente por eso que los analizadores sintácticos de los lenguajes de programación no son autómatas finitos: el anidamiento es libre de contexto por naturaleza.

La escalera completa se resume en una tabla que conviene tener presente, porque cada peldaño se paga con propiedades y no solo con complejidad de implementación.

En el mundo de los statecharts la memoria adicional tiene otro nombre y otra forma. El context de una máquina extendida es un almacén de datos arbitrarios que acompaña al estado de control: un contador de reintentos, una lista de elementos, el cuerpo de una respuesta. Las guardas leen el context para decidir transiciones y las asignaciones lo escriben. Formalmente estamos ante una máquina de estados extendida, y conviene ser explícito sobre lo que eso significa: con un context de contenido ilimitado y guardas arbitrarias sobre él, el modelo deja de estar acotado y se sitúa en potencia junto a un lenguaje de programación cualquiera.

// El control es finito; la memoria que permite CONTAR vive en el context.
const reintentos = {
  initial: "esperando",
  context: { intentos: 0, maximo: 3 },
  states: {
    esperando: {
      on: {
        FALLO: [
          { guard: "quedanIntentos", target: "esperando", actions: "incrementar" },
          {                          target: "agotado" },
        ],
      },
    },
    agotado: { type: "final" },
  },
}

Ese fragmento es la frontera entera en doce líneas. Los estados de control siguen siendo dos y el diagrama sigue siendo legible, pero el comportamiento real depende de un número que el diagrama no muestra. Mientras el context tome un número finito y pequeño de valores relevantes —tres intentos, no más— la máquina extendida es equivalente a una máquina finita con más estados, y podrías desplegarla si quisieras. En cuanto el context guarda algo cuyo tamaño crece con la entrada y las guardas deciden el flujo a partir de ello, ya no hay despliegue posible y las garantías de la clase regular se han ido.

Ese despliegue mental es el mejor instrumento de medida disponible, y vale la pena convertirlo en costumbre. Ante cualquier guarda, pregúntate cuántos estados harían falta para eliminarla codificando la condición en el control. Si la respuesta es tres o cuatro, la máquina sigue siendo esencialmente finita y solo has elegido una notación más compacta; si la respuesta es que dependen del tamaño de la entrada o que directamente son infinitos, has cruzado la frontera. Esa cuenta convierte una cuestión de estilo —cuánto poner en el context— en una pregunta con respuesta numérica.

Existe un tercer camino, intermedio entre la pila y el context sin límites, que la ingeniería usa constantemente sin ponerle nombre teórico: acotar artificialmente lo que era ilimitado. Un validador que solo admite anidamiento hasta profundidad diez sigue siendo un lenguaje regular, porque diez es una constante y el autómata puede tener un estado por nivel. La mayoría de los formatos reales hacen exactamente eso, y la decisión es sensata: recuperas todas las garantías de la clase a cambio de rechazar entradas que en la práctica nadie escribe. Cuando la profundidad debe ser genuinamente arbitraria no hay atajo, pero antes de aceptar esa premisa conviene comprobar si es cierta o solo cómoda.