Autómatas finitos deterministas y no deterministas

El modelo de cómputo más simple que sigue siendo interesante: leer una cadena de izquierda a derecha, sin poder volver atrás, recordando nada más que en qué estado se está. Suena insuficiente y alcanza para validar formatos, reconocer tokens y manejar protocolos.

El determinista, en cinco piezas

Un autómata finito determinista son cinco cosas: estados, alfabeto, función de transición, estado inicial y estados de aceptación. Lee un símbolo, cambia de estado según la función, y al terminar la cadena acepta si quedó en un estado de aceptación.

La restricción central es la memoria: lo único que se recuerda del pasado es el estado actual. Con $k$ estados hay $k$ situaciones distinguibles, ni una más. Por eso puede llevar la cuenta de la paridad de los ceros pero no contar cuántos hubo.

El no determinista y sus caminos en paralelo

La versión no determinista permite varias transiciones para el mismo símbolo, o ninguna, y transiciones que no consumen entrada ($\varepsilon$). Una cadena se acepta si existe al menos un camino que termine aceptando.

No es una máquina realista: nadie construye un dispositivo que adivine. Es una herramienta de descripción, y una muy conveniente, porque expresa “esto o aquello” sin combinar los casos a mano.

Los dos reconocen lo mismo

El resultado central es que no determinista y determinista reconocen exactamente los mismos lenguajes. La construcción de subconjuntos lo demuestra: se simula el autómata no determinista llevando el conjunto de estados en los que podría estar.

Cada conjunto posible es un estado del autómata determinista. La conversión es mecánica, y el costo es que con $n$ estados pueden salir hasta $2^n$. En la práctica casi nunca explota, pero existen lenguajes donde el salto exponencial es inevitable.

El mínimo existe y es único

Para cada lenguaje regular existe un autómata determinista mínimo, y es único salvo el nombre de los estados. Se obtiene agrupando estados indistinguibles: dos estados son equivalentes si ninguna cadena los diferencia en aceptar o rechazar.

Esa unicidad es lo que hace posible comparar lenguajes: dos autómatas reconocen el mismo lenguaje si y sólo si sus mínimos coinciden. El teorema de Myhill-Nerode va más lejos y caracteriza los lenguajes regulares por la cantidad finita de clases de equivalencia.

Cerrados bajo casi todo

Los lenguajes regulares son cerrados bajo casi todo: unión, intersección, complemento, concatenación, estrella. El complemento sale gratis en un determinista completo —intercambiar estados de aceptación—, y por eso la conversión desde no determinista importa: en un no determinista ese truco no funciona.

Además, las preguntas interesantes son decidibles: si el lenguaje es vacío, si es infinito, si dos autómatas son equivalentes. En clases más expresivas eso deja de ser cierto.

Dónde se usan en serio

Aparecen en cualquier lugar donde haya que reconocer patrones con memoria acotada. Los analizadores léxicos convierten expresiones regulares en autómatas y los ejecutan. Los protocolos de red y las máquinas de estados de la interfaz son lo mismo con otro nombre.

Y la limitación es la que hay que tener presente: un autómata finito no cuenta sin límite, no balancea paréntesis y no compara dos mitades de una cadena. Para eso hace falta memoria adicional, que es el capítulo siguiente.

Un autómata es una tabla y un ciclo

type State = 'par' | 'impar';

const transitions: Record<State, Record<string, State>> = {
  par:   { '0': 'par',   '1': 'impar' },
  impar: { '0': 'impar', '1': 'par'   },
};

const accepts = (word: string): boolean => {
  let state: State = 'par';

  for (const symbol of word) {
    const next = transitions[state][symbol];
    if (next === undefined) return false; // símbolo fuera del alfabeto
    state = next;
  }

  return state === 'par'; // el único estado de aceptación
};

Todo el programa son dos cosas: una tabla y un ciclo que la consulta. No hay pila, no hay arreglo, no hay memoria que crezca con la entrada: lo único que se recuerda es en qué estado estamos, y por eso el consumo de memoria es constante sin importar si la cadena tiene diez símbolos o diez millones.

Esa constante es exactamente lo que define la clase: un autómata finito puede llevar la cuenta de la paridad porque son dos situaciones distinguibles, y no puede contar cuántos unos hubo porque eso requeriría un estado por cada cantidad posible.

Determinista o no, y por qué importa poco

La construcción de subconjuntos convierte uno en otro: cada estado del determinista es un conjunto de estados del no determinista, o sea «todos los lugares donde podría estar». Por eso el crecimiento puede ser exponencial, y por eso en la práctica casi nunca lo es.

Cierre

Un autómata finito recuerda un estado y nada más. El no determinismo no agrega poder —la construcción de subconjuntos lo elimina, a costa de un salto exponencial en estados— pero hace mucho más corta la descripción. Y el mínimo, único, es lo que permite decidir equivalencia.