Expresiones regulares y lenguajes regulares

Las expresiones regulares son la parte de la teoría de la computación que todo el mundo usa sin saber que la está usando. Y son un caso raro: la definición formal tiene tres operaciones, mientras que la herramienta que se usa a diario tiene decenas y, en algunos casos, ya no describe lenguajes regulares.

La definición, que es minúscula

La definición es inductiva y minúscula. Son expresiones regulares: el conjunto vacío, la cadena vacía y cada símbolo del alfabeto. Y si $r$ y $s$ lo son, también lo son su unión $r|s$, su concatenación $rs$ y la estrella $r^*$, que es cero o más repeticiones.

Nada más. El + —una o más— es $rr^*$, y el ? es $r|\varepsilon$: azúcar sintáctica, no poder adicional. Con esas tres operaciones se describe toda la clase.

El teorema de Kleene cierra el círculo

El teorema de Kleene cierra el círculo: un lenguaje se describe con una expresión regular si y sólo si lo reconoce un autómata finito. Las dos direcciones son constructivas.

De expresión a autómata, la construcción de Thompson arma un autómata no determinista pieza por pieza, siguiendo la estructura de la expresión. De autómata a expresión, se eliminan estados uno por uno reemplazándolos por expresiones sobre las aristas. Por eso escribir un patrón y compilarlo a una máquina es un procedimiento mecánico.

Dos motores, y uno se cuelga

Hay dos formas de ejecutarlos y la diferencia se paga en producción. El motor tipo autómata simula todos los caminos posibles a la vez y garantiza tiempo lineal en el largo de la entrada.

El motor con retroceso prueba una alternativa, y si falla vuelve atrás y prueba la siguiente. Es más fácil de extender, y es el que puede explotar: hay patrones donde el retroceso tarda tiempo exponencial. Eso es ReDoS, una forma real de tirar abajo un servicio con una cadena de entrada bien elegida.

Lo que las bibliotecas agregaron de más

Las bibliotecas modernas incorporaron cosas que exceden la definición. Las referencias hacia atrás —“esta parte tiene que repetirse igual”— describen lenguajes que no son regulares; con ellas se puede reconocer $ww$, que ningún autómata finito reconoce.

Los lookahead y lookbehind tampoco son parte de la definición, aunque no agregan poder. La conclusión práctica: “expresión regular” en el sentido de la teoría y en el sentido de la biblioteca son dos cosas distintas, y la segunda es la que puede volverse exponencial.

Lo que no se puede, y por qué

Lo que no se puede hacer con una expresión regular genuina es cualquier cosa que requiera contar sin cota o recordar estructura anidada: paréntesis balanceados, HTML, JSON.

La respuesta habitual —“usá un parser”— tiene una razón formal detrás: esos lenguajes son libres de contexto, no regulares, y el modelo de máquina que les corresponde necesita una pila. No es una cuestión de escribir el patrón con más cuidado.

Para lo que sí sirven

Donde sí brillan es en lo que son: validar formatos planos, extraer campos, tokenizar. Un analizador léxico convierte todos sus patrones en un solo autómata y recorre la entrada una vez.

Dos recomendaciones que salen de la teoría. Anclar el patrón reduce drásticamente el retroceso. Y si la entrada viene de afuera, conviene un motor con garantía lineal o un tiempo límite: con retroceso, el peor caso lo elige quien manda la cadena.

Lo que una expresión regular no puede hacer

// Sí: los lenguajes regulares se describen con esto
const email = /^[a-z]+@[a-z]+\.[a-z]{2,}$/; // una forma muy simplificada de correo
const endsInTwoOnes = /^(0|1)*11$/; // termina en dos unos

// No: paréntesis balanceados necesitan contar, y contar no es regular
// No existe ninguna expresión regular que acepte exactamente ((()))
// y rechace ((() — hace falta memoria proporcional a la anidación

// Y esto, que parece regular, no lo es en el sentido formal:
const repeatedWord = /(\w+)\s+\1/; // \1 es una referencia hacia atrás

La última línea es la trampa del tema: lo que los lenguajes llaman «expresiones regulares» tiene extensiones —referencias hacia atrás, anticipación— que no son regulares en el sentido formal. Un autómata finito no puede recordar qué palabra vio para compararla después.

Esas extensiones son útiles y tienen un costo: son justamente las que impiden compilar el patrón a un autómata, y las que obligan al motor a usar retroceso, con el riesgo de tiempo exponencial.

Cuándo conviene y cuándo no

Cierre

Unión, concatenación y estrella: eso son las expresiones regulares, y por el teorema de Kleene describen exactamente lo que reconoce un autómata finito. Las extensiones de las bibliotecas salen de esa clase, y con ellas se va también la garantía de tiempo lineal.