Expresiones regulares
Una expresión regular es una cadena de texto que permite describir un conjunto de palabras. Las expresiones regulares también podemos entenderlas como una forma sencilla de describir un autómata finito.
Qué es una expresión regular
En aritmética usamos símbolos como · y + para formar una expresión como, por ejemplo, (2 + 3) · 4. Al evaluar esta expresión obtenemos un número. Una expresión regular es una sucesión de caracteres y de algunos símbolos especiales, p. ej. a(x ∪ y), cuya evaluación es un lenguaje (formal). El resultado de la expresión (2 + 3) · 4 es el número 20; el resultado de la expresión regular a(x ∪ y) es el conjunto de las dos palabras «ax», «ay».
¿Cómo evaluaríamos la expresión regular anterior a(x ∪ y)? Cada letra es en realidad una abreviatura de un conjunto unitario que contiene esa letra, y la multiplicación oculta es la concatenación de palabras. La expresión regular podríamos reescribirla «en versión completa» así:
Y la evaluaríamos así: la unión {x} ∪ {y} nos da el lenguaje {x,y}. Concatenando los lenguajes {a} y {x,y} obtenemos el lenguaje {ax, ay}.
Las expresiones regulares se utilizan muchísimo en programación y la mayoría de los lenguajes de programación las tienen implementadas de un modo u otro. Se usan, por ejemplo, para comprobar si un texto introducido por el usuario cumple ciertos criterios (p. ej., si es un correo electrónico válido, una fecha válida, etc.) o para sustituir textos (por ejemplo, podemos querer sustituir todas las apariciones de una URL en un texto por enlaces en los que se pueda hacer clic).
Las implementaciones reales de las expresiones regulares suelen ser más potentes que las expresiones regulares aquí descritas y utilizan una sintaxis algo distinta, pero sobre todo más complicada.
Definición de expresión regular
Definiremos la expresión regular sobre un alfabeto Σ. Entonces diremos que una expresión regular es:
- a, donde a ∈ Σ. Es decir, un símbolo del alfabeto por sí solo es una expresión regular.
- ϵ: la palabra vacía; en programación se escribe también como unas comillas vacías «».
- ∅: una expresión regular debe poder describir también el lenguaje vacío, así que el lenguaje vacío es una expresión regular.
- (R1 ∪ R2), donde R1, R2 son expresiones regulares.
- (R1 ∘ R2), donde R1, R2 son expresiones regulares.
- (R∗), donde R es una expresión regular.
En lugar del símbolo ∪ del punto 4 podemos usar también la barra vertical: ∣. En lugar del símbolo ∘ no hace falta usar nada. Igual que normalmente no escribimos el símbolo de la multiplicación, el punto ·, tampoco solemos escribir el símbolo de la concatenación ∘. Estas expresiones regulares son, pues, idénticas: a ∘ (b ∪ c) y a(b ∣ c).
¿Qué significa cada operador?
- ∪ o ∣ denota la unión de lenguajes.
- ∘ denota la concatenación de lenguajes.
- ∗ denota la clausura de un lenguaje.
Ejemplos:
- a denota el lenguaje sencillo {a}.
- a ∣ b denota el lenguaje formado por las dos palabras {a, b}.
- a ∘ b denota el lenguaje {ab}.
- a(b ∣ c)d denota el lenguaje {abd, acd}.
- a(b∗) denota el lenguaje de todas las palabras que empiezan por la letra «a», seguida de una cantidad cualquiera de letras «b».
- (ab)∗ denota el lenguaje de todas las palabras {ϵ, ab, abab, ababab, …}.
- 0∗10∗ denota el lenguaje de todas las palabras binarias que contienen exactamente un uno. (Fíjate en que sería más exacto escribir esta expresión así: (0∗)1(0∗), pero si la notación se lee bien sin paréntesis, podemos omitirlos.)
- Σ∗1Σ∗ denota el lenguaje de todas las palabras que contienen al menos un uno.
- (1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9)(0 ∣ 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9)∗ denota el lenguaje de todos los números naturales.
A continuación mostraremos la equivalencia entre las expresiones regulares y los autómatas finitos. Para cada expresión regular cuya evaluación es el lenguaje R existe un autómata finito A que cumple L(A) = R, y viceversa.
Fuentes
Capítulos: Expresiones regulares, Conversión de una expresión regular en un autómata, Autómata finito no determinista generalizado, Conversión de un autómata en una expresión regular
