Los autómatas finitos son máquinas abstractas que leen símbolos y cambian de estado. Permiten definir lenguajes, validar secuencias, analizar texto y modelar procesos con una cantidad limitada de memoria.
Un autómata es un modelo matemático de computación. Recibe una entrada símbolo por símbolo, conserva un estado interno y sigue reglas de transición hasta decidir si acepta o rechaza la cadena.
Este modelo no pretende representar toda la potencia de una computadora. Su restricción a una cantidad finita de estados lo hace ideal para patrones regulares, validación de formatos, analizadores léxicos y controladores.
Un alfabeto, normalmente denotado Σ, es un conjunto finito de símbolos. Una cadena es una secuencia finita de símbolos del alfabeto.
La cadena vacía se denota ε y tiene longitud cero. Pertenece a Σ* para cualquier alfabeto, donde Σ* representa el conjunto de todas las cadenas finitas construidas con Σ.
Un lenguaje formal es cualquier subconjunto de Σ*. No se define por significado humano, sino por las cadenas que contiene.
Una gramática, una expresión regular o un autómata son distintas formas de especificar un lenguaje. Los autómatas finitos reconocen una familia importante llamada lenguajes regulares.
Un autómata finito determinista se define mediante una quíntupla:
La función δ indica a qué estado se pasa al leer cada símbolo. El estado resume toda la información del pasado que el autómata necesita para continuar.
El autómata comienza en q0 y procesa la cadena de izquierda a derecha. Después de consumir todos los símbolos, acepta si el estado actual pertenece a F.
Una cadena puede recorrer estados aceptadores en el medio y terminar rechazada; lo único decisivo es el estado después de leer toda la entrada.
Un autómata finito determinista, AFD o DFA, tiene exactamente una transición definida para cada combinación de estado y símbolo de entrada.
El determinismo hace que una cadena tenga un único recorrido posible. Un AFD puede implementarse directamente con una tabla de transiciones o un mapa de estados.
Construyamos un AFD sobre {0, 1} que acepte cadenas con una cantidad par de unos. Solo hace falta recordar si hasta ahora se vio una cantidad par o impar de unos.
| Estado actual | Con 0 | Con 1 | ¿Acepta? |
|---|---|---|---|
| par | par | impar | Sí |
| impar | impar | par | No |
Leer un cero no cambia la paridad. Leer un uno alterna entre estados. El estado inicial es par porque antes de leer símbolos hay cero unos, y cero es par.
Para la cadena 1010, el recorrido es: par → impar → impar → par → par. El estado final es par, por lo tanto la cadena se acepta.
Para 101, el estado final es impar y la cadena se rechaza. El autómata no necesita recordar la posición ni contar todos los unos: dos estados bastan para conservar la paridad.
function acepta(afd, cadena) {
let estado = afd.inicial;
for (const simbolo of cadena) {
const transiciones = afd.transiciones.get(estado);
if (!transiciones || !transiciones.has(simbolo)) return false;
estado = transiciones.get(simbolo);
}
return afd.aceptacion.has(estado);
}
const paridadUnos = {
inicial: "par",
aceptacion: new Set(["par"]),
transiciones: new Map([
["par", new Map([["0", "par"], ["1", "impar"]])],
["impar", new Map([["0", "impar"], ["1", "par"]])]
])
};
console.log(acepta(paridadUnos, "1010")); // true
console.log(acepta(paridadUnos, "101")); // falseEn un AFD completo cada estado debe tener transición para todos los símbolos del alfabeto. Si un formato no permite cierto carácter, se puede usar un estado de rechazo explícito o rechazar al no encontrar transición.
Un estado sumidero recibe entradas inválidas y permanece en rechazo para cualquier símbolo posterior. Permite que la función de transición sea total sin perder la decisión de rechazo.
Este estado es útil al convertir una especificación informal en un AFD formal. En una implementación práctica, devolver rechazo inmediato puede ser más directo si no se necesita observar el recorrido completo.
Un autómata finito no determinista, AFN o NFA, puede tener cero, una o varias transiciones para un mismo par de estado y símbolo. También puede incluir transiciones ε que no consumen símbolo.
El no determinismo es una herramienta de descripción, no una capacidad mágica de ejecución. Todo AFN tiene un AFD equivalente, aunque la conversión puede aumentar la cantidad de estados.
La construcción por subconjuntos construye estados de un AFD que representan conjuntos de estados posibles del AFN. Con transiciones ε se calcula además la clausura ε de cada conjunto.
La equivalencia entre AFD y AFN muestra que ambos reconocen exactamente los lenguajes regulares. La diferencia principal está en comodidad de diseño y costo de la representación.
Una expresión regular describe patrones de cadenas mediante concatenación, alternativa y repetición. Para lenguajes regulares, expresiones regulares y autómatas finitos tienen el mismo poder expresivo.
Las expresiones regulares son cómodas para patrones compactos. Los autómatas son útiles para visualizar estados, procesar entrada incrementalmente y demostrar propiedades. El próximo tema profundizará en gramáticas y expresiones regulares.
Un compilador o intérprete separa el texto fuente en tokens: identificadores, números, palabras reservadas, operadores y espacios. Muchos de esos patrones son regulares y se reconocen con autómatas.
Reconocer tokens no es lo mismo que validar toda la sintaxis del lenguaje. Las estructuras anidadas, como paréntesis balanceados arbitrariamente, requieren modelos con memoria adicional.
Los AFD son apropiados para validar secuencias con reglas locales: códigos con prefijo, estados de un formulario, protocolos simples y formatos de entrada acotados.
Una validación real suele sumar límites de longitud, normalización, contexto de negocio y mensajes de error. El autómata modela la regla de secuencia, no todas las políticas del sistema.
Una interfaz, un pedido o un protocolo también puede modelarse con estados y transiciones. La diferencia con un reconocedor formal es que las transiciones pueden ejecutar acciones y las entradas pueden ser eventos complejos.
Hacer explícita la máquina de estados evita combinaciones imposibles, facilita las pruebas y ayuda a documentar qué eventos cambian realmente el estado de un proceso.
Un autómata finito tiene memoria limitada a su estado, por lo que no puede recordar una cantidad arbitraria. No puede reconocer, por ejemplo, el lenguaje de paréntesis correctamente balanceados con profundidad sin límite.
También escapan a los autómatas finitos lenguajes como {anbn | n ≥ 0}. Conocer estos límites ayuda a no resolver un problema de sintaxis compleja con una expresión regular inadecuada.
Combinar reglas puede multiplicar la cantidad de estados. Si un autómata controla dos propiedades independientes con m y n estados, su producto puede necesitar hasta m·n estados para recordar ambas.
La minimización de autómatas busca reducir estados equivalentes sin cambiar el lenguaje reconocido. En implementaciones, a veces una tabla clara vale más que una minimización difícil de mantener.
El objetivo es que cada estado tenga una interpretación legible. Un diagrama con nombres como esperandoDígito suele ser más fácil de revisar que estados numerados sin significado.
Los autómatas no sustituyen toda la lógica de una aplicación, pero ofrecen una base precisa cuando el comportamiento depende de una secuencia de símbolos o eventos y de un número finito de estados.
Los autómatas convierten patrones y secuencias en reglas exactas de transición. En el próximo tema estudiaremos gramáticas y expresiones regulares, dos lenguajes complementarios para describir conjuntos de cadenas.