Portada
Tabla de contenido
Expresiones regulares..................................................................................................................3
La Semántica de las Expresiones Regulares...............................................................................3
Construcción de expresiones regulares.....................................................................................4
Conjuntos Regulares....................................................................................................................4
Bibliografía..................................................................................................................................5
Expresiones regulares
Una expresión regular es una forma de representar los lenguajes regulares, y se
construye utilizando caracteres del alfabeto sobre el cual se define el lenguaje.
Llamaremos expresión regular sobre el alfabeto Σ a toda palabra sobre el alfabeto
Σ1 definido por la siguiente igualdad:
Σ1 := {∅, λ, +, ·,(,), ∗ } ∪ Σ,
conforme a las reglas siguientes:
Son expresiones regulares ∅, λ, a para cualquier símbolo a en el alfabeto Σ.
Si α y β son expresiones regulares, también lo son:
o (α + β) es una expresión regular,
o (α · β) es una expresión regular,
o (α) ∗ es una expresión regular
Tomemos el alfabeto Σ := {a, b}. Son expresiones regulares las secuencias de
símbolos (palabras) siguientes: a · a + b ∗a, ab∗ba,
La Semántica de las Expresiones Regulares
Sea Σ un alfabeto finito. A cada expresión regular sobre el alfabeto α le
asignaremos un lenguaje formal L(α) ⊆ Σ ∗ conforme a las siguientes reglas:
Aplicando las reglas recursivas, si α y β son dos expresiones regulares sobre el
alfabeto Σ usaremos las reglas siguientes:
L(α + β) = L(α) ∪ L(β),
L(α · β) = L(α) · L(β),
L(α ∗ ) = L(α) ∗ .
También mencionamos que el operador ∗ tiene preferencia sobre · y éste sobre +.
Ejemplo: sea α := 0 ∗10∗ la expresión regular sobre el alfabeto Σ := {0, 1}.
Entonces, L(0 ∗10∗ ) = L(0) ∗ · L(1) · L(0) ∗ = {0 m10n : n, m ∈ N}.
Construcción de expresiones regulares
Expresiones básicas:
Las constantes ϵ y ∅ son expresiones regulares, que representan a los lenguajes
{ϵ} y ∅ respectivamente. Es decir, L(ϵ) = {ϵ} y L(∅) = ∅.
Si a es cualquier símbolo, entonces a es una expresión regular. Esta expresión
representa el lenguaje {a}. Es decir, L(a) = {a}.
Una variable, normalmente escrita en mayúsculas e itálicas, representa cualquier
lenguaje.
Operadores:
Si E y F son expresiones regulares, entonces E + F es una expresión regular que
representa la unión de L(E) y L(F). Es decir, L(E + F) = L(E) ∪ L(F).
Si E y F son expresiones regulares, entonces EF es una expresión regular que
representa la concatenación de L(E) y L(F).
Si E es una expresión regular, entonces E* es una expresión regular, que
representa la clausura de L(E). Es decir, L(E∗) = L(E)* (clausura del lenguaje E).
También se pueden usar paréntesis.
Conjuntos Regulares
Un conjunto regular es cualquier conjunto definido solamente a partir de
concatenación, unión y la operación estrella sobre conjuntos regulares.
Un conjunto regular puede estar definido por dos expresiones regulares, como por
ejemplo 1∗ y (1 ∗ ) ∗
Bibliografía
Blog. (2019). Obtenido de [Link]
5_Expresiones_regulares.pdf
BLOG. (21 de Septiembrre de 2021). Obtenido de
[Link]
