Lenguajes regulares: lo que una FSM reconoce · Máquinas de Estado

Una máquina de estados finita no reconoce cualquier cosa: reconoce exactamente una clase de lenguajes, ni uno más ni uno menos, y esa clase tiene una descripción alternativa que probablemente uses a diario sin llamarla por su nombre. Que los autómatas finitos y las expresiones regulares denoten el mismo conjunto de lenguajes es uno de esos teoremas que parecen técnicos y resultan ser el fundamento de media caja de herramientas: analizadores léxicos, validadores, resaltado de sintaxis, motores de búsqueda. Y su reverso vale igual: cuando algo escapa de esa clase, ninguna cantidad de ingenio en la expresión regular lo va a rescatar, porque la imposibilidad no está en el patrón sino en la máquina que lo ejecuta.

🎯 Al terminar esta lección sabrás

Definir con precisión lenguaje regular y situarlo como el nivel más bajo de la jerarquía de Chomsky.
Recorrer el teorema de Kleene y las tres construcciones que cierran el triángulo regex, NFA, DFA.
Usar las propiedades de cerradura, en especial el autómata producto y el complemento.
Reconocer qué construcciones de un motor de regex moderno ya no son regulares y qué cuesta eso.

La clase regular, definida por dentro y por fuera

Fijemos el vocabulario, que aquí paga. Un alfabeto es un conjunto finito de símbolos; una cadena es una secuencia finita de símbolos; Σ* es el conjunto de todas las cadenas posibles sobre Σ, incluida la vacía; y un lenguaje es simplemente un subconjunto de Σ*. Nada más. Un lenguaje puede ser finito o infinito, y la inmensa mayoría de los lenguajes sobre un alfabeto son inexpresables por cualquier medio finito, hecho que conviene tener presente para no sorprenderse de que existan límites.

Un lenguaje es regular si existe algún autómata finito determinista que lo reconoce. Es una definición por dentro: describe la clase por la maquinaria que la decide. La lección anterior nos autoriza a decir también que basta con exhibir un NFA, porque la construcción de subconjuntos garantiza un DFA equivalente. Y el teorema de Kleene añadirá una tercera formulación, esta vez por fuera: describir la clase por la notación que la denota, sin hablar de máquinas.

Los lenguajes regulares ocupan el peldaño más bajo de la jerarquía de Chomsky, el tipo 3. Por encima están los lenguajes libres de contexto, reconocidos por autómatas con pila; después los sensibles al contexto; y arriba los recursivamente enumerables de la máquina de Turing. Cada peldaño añade memoria, y cada peldaño paga esa memoria con propiedades que pierde: la clase regular es la única en la que la equivalencia entre dos máquinas es decidible con eficiencia razonable, y esa es una moneda de cambio muy real.

ℹ️

Regular no significa sencillo, significa acotado

Un lenguaje regular puede ser infinito y visualmente intrincado; lo que no puede es exigir memoria que crezca con la entrada. La marca distintiva de la clase es esa: existe una cota fija de información sobre el pasado —el estado actual, elegido entre un conjunto finito— que basta para decidir el resto. Toda la teoría de esta lección se deduce de esa única restricción, y también todas las imposibilidades de la siguiente. Cuando te preguntes si algo es regular, no mires si el patrón parece complicado: pregúntate cuánta información del prefijo ya leído hace falta recordar, y si esa cantidad depende de la longitud de la entrada.

El teorema de Kleene y el triángulo de construcciones

Stephen Kleene demostró en 1956 que la clase de lenguajes reconocidos por autómatas finitos coincide exactamente con la clase denotada por las expresiones regulares. La notación se define con una inducción minúscula: son expresiones el lenguaje vacío, la cadena vacía y cada símbolo del alfabeto; y a partir de ahí se combinan por unión, por concatenación y por estrella de Kleene —cero o más repeticiones—. Tres operadores y tres casos base bastan para denotar toda la clase.

La demostración se completa con tres construcciones efectivas que forman un triángulo. La de Thompson traduce una expresión regular en un NFA con transiciones épsilon, componiendo autómatas pequeños con el pegamento de las aristas que no consumen entrada. La de subconjuntos determiniza ese NFA. Y la eliminación de estados —también llamada algoritmo de Kleene— recorre el camino inverso, colapsando estados de un autómata y etiquetando las aristas con expresiones cada vez mayores hasta dejar una sola.

flowchart LR
R[expresion regular] -->|construccion de Thompson| N[NFA con epsilon]
N -->|construccion de subconjuntos| D[DFA]
D -->|eliminacion de estados| R
D -->|Myhill Nerode| M[DFA minimo unico]
style R fill:#cba6f7,color:#11111b
style D fill:#89b4fa,color:#11111b
style M fill:#a6e3a1,color:#11111b

La flecha extra hacia el DFA mínimo merece un comentario, porque es la que da a la clase su propiedad más útil en la práctica. Todo lenguaje regular tiene un DFA mínimo y ese autómata es único salvo renombrado de estados, resultado que se sigue del teorema de Myhill y Nerode. La consecuencia operativa es enorme: para decidir si dos expresiones regulares denotan el mismo lenguaje basta con minimizar ambos autómatas y comparar. Ninguna clase superior de la jerarquía ofrece nada parecido; la equivalencia de dos gramáticas libres de contexto es directamente indecidible.

La minimización se calcula con el algoritmo de Hopcroft en tiempo casi lineal, o con el más didáctico de refinamiento de particiones: se empieza separando aceptadores de no aceptadores y se van partiendo los bloques en los que dos estados se comportan distinto ante algún símbolo, hasta que ninguna partición cambia. Lo que queda al final son las clases de equivalencia de estados indistinguibles, y ese es el autómata canónico del lenguaje. Que exista una forma canónica es una rareza que conviene apreciar: significa que la pregunta por la identidad de dos objetos definidos de forma completamente distinta se responde reduciendo ambos a una misma representación y comparándola.

Un aviso para no idealizar el triángulo: las tres construcciones son efectivas, pero no todas son baratas ni todas conservan el tamaño. La eliminación de estados puede producir expresiones regulares astronómicas a partir de autómatas modestos, hasta el punto de que el tamaño de la expresión mínima puede ser exponencial en el número de estados. La equivalencia de los formalismos es un hecho sobre qué se puede expresar, no una promesa de que la traducción sea cómoda en ambos sentidos. En ingeniería se recorre casi siempre en la dirección barata —de la expresión al autómata— y rara vez en la contraria.

Cerradura: el álgebra que hace componible la clase

Una clase de lenguajes se vuelve una herramienta de ingeniería cuando es cerrada bajo operaciones, es decir, cuando combinar dos miembros produce otro miembro. Los lenguajes regulares lo son bajo prácticamente todo lo que se le ocurre a uno, y cada cerradura viene con una construcción explícita que se puede programar.

operación	construcción	coste en estados
unión `L1 \| L2`	autómata producto o NFA con dos ramas	`n · m` o `n + m + 1`
intersección	autómata producto con aceptación conjunta	`n · m`
complemento	intercambiar `F` en un DFA completo	`n`
concatenación	épsilon desde los finales de `L1` al inicio de `L2`	`n + m`
estrella	épsilon de vuelta al inicio más un estado nuevo	`n + 1`
inversión	invertir aristas, intercambiar inicial y finales	`2^n` en el peor caso

El autómata producto se programa casi tan rápido como se describe, y tenerlo escrito ayuda a ver que la intersección no es una operación abstracta sino dos máquinas ejecutándose al unísono sobre la misma cinta.

type DFA<E extends string, S extends string> = {
  delta: Record<E, Record<S, E>>
  inicial: E
  finales: ReadonlySet<E>
}

// Producto: el estado es el par, y el criterio de aceptacion elige la operacion.
function producto<A extends string, B extends string, S extends string>(
  m1: DFA<A, S>, m2: DFA<B, S>, simbolos: S[], conjuncion: boolean,
) {
  const paso = (par: [A, B], s: S): [A, B] => [m1.delta[par[0]][s], m2.delta[par[1]][s]]
  const aceptaPar = (par: [A, B]) =>
    conjuncion
      ? m1.finales.has(par[0]) && m2.finales.has(par[1])   // interseccion
      : m1.finales.has(par[0]) || m2.finales.has(par[1])   // union
  return { inicial: [m1.inicial, m2.inicial] as [A, B], paso, acepta: aceptaPar, simbolos }
}

El autómata producto merece atención porque su idea reaparece en todo el track. Para reconocer la intersección de dos lenguajes se ejecutan los dos autómatas a la vez sobre la misma entrada, y el estado del producto es el par formado por el estado de cada uno; se acepta cuando ambas componentes están en sus respectivos F. Cambiando el criterio de aceptación a que lo esté al menos una se obtiene la unión. Esa construcción, con su recuento de n · m estados, es exactamente la explosión combinatoria que en el nivel de los statecharts se domestica con regiones ortogonales: la región paralela es un autómata producto al que se le ha ahorrado el escribir el producto.

El complemento es el caso donde la letra pequeña muerde. Intercambiar los estados aceptadores por el resto solo produce el complemento si el autómata es completo, porque una cadena que se atascaba en una máquina parcial no estaba siendo rechazada por ningún estado al que darle la vuelta. Totalizar primero con un sumidero y complementar después es correcto; hacerlo al revés no. Es la misma advertencia de la lección 1, ahora con una consecuencia visible.

Hay además una asimetría de coste que conviene tener presente al componer. Complementar un DFA es gratis en estados, pero complementar un NFA obliga a determinizarlo primero, y por tanto arrastra el coste exponencial de la lección anterior. Lo mismo ocurre con la inversión: invertir las aristas de un DFA produce un NFA, no un DFA, y volver a determinizar puede multiplicar los estados. Por eso el orden en que se encadenan operaciones importa tanto como cuáles se usan, y una cadena de complementos e intersecciones escrita sin cuidado puede pasar de instantánea a inviable sin que ninguna de sus piezas parezca sospechosa.

La cerradura tiene también una lectura de diseño que trasciende la teoría. Que la clase sea cerrada significa que se puede razonar por partes: validar un formato complejo como la intersección de tres reglas simples, cada una escrita y probada por separado, sabiendo de antemano que la combinación seguirá siendo decidible en un paso por carácter. Esa composicionalidad es lo que separa una técnica utilizable de una curiosidad: sin ella, cada regla nueva obligaría a rehacer el análisis del conjunto.

💡

Las decisiones también son cerradas, y eso vale dinero

La cerradura no solo produce lenguajes: produce algoritmos. Como la clase es cerrada bajo intersección y complemento, y como decidir si un autómata reconoce el lenguaje vacío es un simple recorrido de alcanzabilidad, se obtienen gratis decisiones que en clases superiores son imposibles. Contención de un lenguaje en otro: comprueba que la intersección con el complemento del segundo sea vacía. Equivalencia: doble contención, o minimización y comparación. Finitud: busca un ciclo alcanzable desde el inicio y coalcanzable a un final. Todo esto es lo que permite a un analizador léxico avisarte de que dos reglas se solapan, o a una herramienta de rutas detectar que un patrón nunca se alcanzará porque otro anterior lo cubre entero.

Lo que tu motor de expresiones regulares hace de más

Aquí llega la disonancia que causa más confusión práctica. Las expresiones regulares de la teoría son las de Kleene: unión, concatenación y estrella. Las de un lenguaje de programación moderno traen extensiones que salen de la clase, y ese salto no es gratuito ni cosmético.

Lo que sigue siendo regular es casi todo el azúcar sintáctico: las clases de caracteres, los cuantificadores acotados, la opcionalidad, el más, los anclajes de principio y fin. Todo eso se traduce mecánicamente a los tres operadores básicos y no cambia la clase. Incluso las lookarounds —anticipación y retrospección— preservan la regularidad, porque equivalen a intersecciones y complementos, aunque su implementación con backtracking sea costosa.

Lo que rompe la clase son las referencias hacia atrás. Un patrón que exige que un fragmento se repita idéntico más adelante obliga a recordar ese fragmento entero, y su longitud no está acotada. El lenguaje de las cadenas de la forma ww no es regular, y sin embargo cualquier motor con backreferences lo expresa en unos pocos caracteres. Ese motor, por tanto, no está reconociendo lenguajes regulares: está ejecutando un algoritmo de búsqueda con backtracking cuyo peor caso es exponencial, y de ahí nacen las vulnerabilidades por denegación de servicio sobre expresiones regulares que todavía en 2026 tumban servicios reales.

// Regular: se traduce a union, concatenacion y estrella sin perder nada.
const hexadecimal = /^#?[0-9a-f]{6}$/i

// NO regular: la referencia hacia atras exige recordar el grupo capturado.
const repetido = /^(a+)\1$/

// El peor caso clasico: anidar cuantificadores invita al backtracking catastrofico.
const peligroso = /^(a+)+$/

✅

Sigue siendo regular

Clases de caracteres, cuantificadores acotados, opcionalidad, anclajes e incluso las lookarounds. Todo se reduce a los tres operadores de Kleene.

⛔

Sale de la clase

Las referencias hacia atrás. Exigen recordar un fragmento de longitud no acotada, y ninguna máquina finita puede hacerlo.

⏱️

Y cambia el contrato

Fuera de la clase se pierde la garantía de tiempo lineal. El peor caso pasa de acotado a exponencial sobre entradas de pocas decenas de caracteres.

La ingeniería que resuelve esto está bien establecida. Motores como RE2, el paquete regex de Rust o el motor de Go renuncian deliberadamente a las backreferences para no salir de la clase regular, y a cambio garantizan tiempo lineal en la longitud del texto mediante determinización perezosa. La decisión es explícita y es la correcta cuando el patrón puede venir de un usuario. En el navegador, donde el motor nativo sí hace backtracking, la mitigación pasa por acotar la entrada, evitar cuantificadores anidados y tratar los patrones dinámicos como lo que son: código de origen externo.

⚠️

La imposibilidad es del modelo, no del patrón

Cuando descubras que no consigues validar algo con una expresión regular, la primera pregunta no debe ser cuál es el truco que te falta, sino si lo que intentas reconocer es regular. Emparejar delimitadores anidados a profundidad arbitraria, validar HTML, comprobar que un número de aperturas coincide con el de cierres: nada de eso es regular, y por tanto ninguna expresión regular en el sentido de Kleene lo hará jamás. Insistir con backreferences o con lookarounds cada vez más retorcidos consigue a veces un patrón que funciona en los casos de prueba y falla en producción con un coste exponencial. La respuesta correcta es cambiar de herramienta: un analizador sintáctico de verdad, o una máquina con memoria adicional. La lección siguiente demuestra por qué esa frontera es infranqueable y no una cuestión de esfuerzo.

⚡

Regular no es una etiqueta de potencia: es un contrato de coste

La forma superficial de entender los lenguajes regulares es como el escalón débil de una escala, lo que se puede hacer cuando no se puede hacer nada mejor. La forma que cambia decisiones es verlos como un contrato con cláusulas concretas, cada una comprada con una renuncia. La cláusula central dice que decidir la pertenencia cuesta un paso por símbolo y memoria constante, independientemente de la longitud de la entrada y del tamaño del patrón: es la garantía que permite ejecutar un léxico sobre megabytes o un validador sobre entrada hostil sin pensar en el peor caso. La segunda cláusula dice que la clase es cerrada, de modo que componer dos validadores sigue produciendo un validador con las mismas garantías, algo que no se puede dar por hecho en ninguna clase superior. Y la tercera, la más infravalorada, dice que las preguntas sobre la propia máquina son decidibles: puedes preguntar si dos patrones son equivalentes, si uno contiene al otro, si alguno es inalcanzable, y obtener respuesta. Ninguna de esas tres cláusulas sobrevive a añadir memoria. En cuanto un modelo puede contar, la equivalencia se vuelve indecidible, la composición deja de ser inocente y el coste deja de estar acotado. Por eso la elección entre quedarse en la clase regular o salir de ella nunca es una elección sobre qué eres capaz de reconocer: es una elección sobre qué garantías estás dispuesto a perder a cambio. Y por eso los motores serios de 2026 renuncian voluntariamente a expresividad que técnicamente podrían ofrecer. Prefieren un contrato que se cumple siempre a un poder que a veces cuesta lo que nadie puede pagar.

⚔️ Explora la clase y sus bordes

Escribe la expresión regular y el DFA de las cadenas sobre a, b con un número par de a. Comprueba que el autómata tiene dos estados y explica por qué no puede tener menos.
Construye el autómata producto de ese lenguaje con el de las cadenas que terminan en b, y anota cuántos estados tiene la intersección frente a los factores.
Complementa un autómata parcial sin totalizarlo y encuentra una cadena concreta que revele el error. Después totalízalo y repite.
Traduce a mano una expresión con la construcción de Thompson y cuenta las transiciones épsilon generadas; después elimínalas con la clausura.
Demuestra que el lenguaje de las cadenas de la forma ww no puede reconocerse con memoria acotada, argumentando cuántos prefijos hay que distinguir.
Mide en tu entorno el tiempo de /^(a+)+$/ sobre una cadena de treinta a seguidas de una b, y repítelo con un motor sin backtracking. Anota los dos órdenes de magnitud.