Clase 05

Compiladores
Expresiones Regulares
By Adolfo Jiménez Ch.

2015

Expresión Regular
• Alfabeto (Σ). Conjunto finito, no vacío, de
elementos.
• Los elementos se denominan letras o
símbolos.




Los alfabetos español, inglés, o alemán.
Σ1 = {0, … , 9}, 0 ϵ Σ1
Σ2 = {x | x es un símbolo del código ASCII}
Σ3 = {(, )}
Σ4 = {a, b, c ,d}

Expresión Regular
• Palabra. Sea un alfabeto Σ. Unapalabra
sobre Σ es una secuencia finita de las
letras de ese alfabeto.
• La secuencia vacía representa la palabra
vacía y se representa con Ɛ.
• El conjunto de palabras (w) tal que:
• {w|w consta de unnúmero igual de ceros que de
unos}.
• {w|w es un entero binario que es primo }.
• {w|w es un programa C sintácticamente correcto }.

Expresión Regular
• Lenguaje(L). Cualquier conjunto contable
de cadenassobre algún alfabeto Σ.
• Las expresiones regulares operan con
lenguajes, utilizando las operaciones
unión, concatenación y estrella de Kleene.
• Cada expresión regular representa un
lenguaje definidosobre un alfabeto Σ.
• Si a es un símbolo en Σ, entonces a es
una expresión regular, y L(a) = {a}.

Ejemplos:
• El lenguaje de todas las cadenas que
constan de n ceros seguidos de n unos
paracualquier n ≥ 0:
• {ε ,01,0011,000111,. . .}

• El conjunto de cadenas formadas por el
mismo número de ceros que de unos:
• {ε ,01,10,0011,0101,1001, . . .}

• El conjunto de números binarios cuyo
valor esun número primo:
• {10,11,101,111,1011, . . .}

Ejemplos:
• Σ* es un lenguaje para cualquier alfabeto
Σ.
• Ø, el lenguaje vacío, es un lenguaje de
cualquier alfabeto.
• {ε}, el lenguaje que constasólo de la
cadena vacía, también es un lenguaje de
cualquier alfabeto. Observe que Ø ≠ {ε}; el
primero no contiene ninguna cadena y el
segundo sólo tiene una cadena.

Operaciones básicas con ER
•(r)|(s) es una ER que denota el lenguaje L(r)
U L(s).
• (r)(s) es una ER que denota el lenguaje
L(r)L(s).
• (r)* es una ER que denota a (L(r))*.
• (r) es una ER que denota a L(r). Esta última
regla dice...