PDF de programación - Las Expresiones Regulares

1 Clase 3 SSL



EXPRESIONES REGULARES

Para REPRESENTAR a los Lenguajes Regulares.
Se construyen utilizando los caracteres del alfabeto sobre el cual se define el lenguaje, el símbolo  y
operadores especiales. Concatenación (), que ordena la ubicación de ciertos caracteres, unión (+),
que representa una elección entre caracteres o grupos de caracteres y Clausura *

La Expresión Regular a representa al Lenguaje Regular que contiene solamente la palabra a, es decir:
L = {a}.
La Expresión Regular  representa al Lenguaje Regular que solo contiene la palabra vacía: L = {}.
La Expresión Regular ab representa el LR de una sola palabra, L = {ab}.
La ER a+ba, describe la posibilidad de elegir entre dos palabras: la palabra a o la palabra ba. L= {a,
ba}.
La operación de “unión” es conmutativa. Por consiguiente, las ERs a+ba y ba+a representan el
mismo LR.
La ER ab + , representa L = {, ab}.

La factorización
La ER abb+aab tiene el prefijo a y el sufijo b se puede “factorizar a izquierda y a derecha”,
obteniendo, así, la ER a(b+a)b.
La ER abbaac+abac+abacccac. se puede factorizar y reescribir ab(ba++accc)ac.

Dos Expresiones Regulares son EQUIVALENTES si representan el mismo Lenguaje Regular.
Las ERs a+b y b+a son equivalentes porque ambas representan al LR {a, b}.
Las ERs a(a+b) y (a+b)a no son equivalentes.


EL OPERADOR POTENCIA

La ER +(a+b)3 representa al LR: “La palabra vacía y todas las palabras de tres caracteres sobre el
alfabeto {a, b}”.
El lenguaje “Todas las palabras de longitud 27 sobre el alfabeto {a, b} y que comienzan con 25 aes” se
puede representar fácilmente mediante la siguiente ER: a25(a+b)2.

No todos los LRs finitos se representan mejor con ERs. Observe el siguiente ejemplo:

Sea el lenguaje L = {an / 1  n  1000}. Este es un LR finito y, por lo tanto, puede ser representado
por una ER. Dado que el lenguaje L tiene 1000 palabras, la ER que lo representa deberá tener 1000
términos, es decir:
a + aa + aaa + ... + a999 + a1000

EXPRESIONES REGULARES PARA LENGUAJES REGULARES INFINITOS
El operador estrella de Kleene o clausura de Kleene genera la palabra vacía y todas las palabras que
se forman con la repetición, de su operando, un número de veces a elección.
La ER a*, que corresponde a la expresión infinita  + a + aa + aaa + aaaa + ... L = {an / n  0},
La ER aa* corresponde a la expresión infinita a + aa + aaa + aaaa + ..., L = {an / n  1},
que podemos describir mediante la frase: “Todas las palabras formadas solo por aes”.

2 Clase 3 SSL

Los operadores “estrella de Kleene”, concatenación y unión son los tres operadores ORIGINALES e
indispensables para construir cualquier ER.
Un nuevo operador “no básico”, es clausura positiva, se representa mediante un símbolo + así: a+.
Se utiliza para simplificar la escritura de ERs como la del Ejemplo aa* o a*a.
Las siguientes ERs son equivalentes:
 = * = +.
a*a* = a*;
a+ = aa* = a*a = aa*a* = a+a* = a*a+ = a*a*aa*, entre otras.
(+a)* = (+a)+ = a*


LA EXPRESIÓN REGULAR UNIVERSAL Y SU APLICACIÓN
Representa al Lenguaje Universal sobre un alfabeto dado.
Ejemplo 25
Si el alfabeto es {a,b}, la ERU es (a+b)*.
Si el alfabeto es {0,1}, la ERU es (0+1)*.
Si el alfabeto es {a,b,c}, la ERU es (a+b+c)*.
Ejemplo
Todas las palabras sobre el alfabeto {a,b} que comienzan con a”, ER: a(a+b)*.
Todas las palabras que comienzan con a, sobre el alfabeto {a,b,c}”, a(a+b+c)*.
Sea  = {a,b} y sea el LR: “Todas las palabras que comienzan con una a y terminan con otra a”. ER
a(a+b)*a.
“Todas las palabras que terminan con aa o con bb” se representa mediante la ER (a+b)*(aa+bb).
 = {a, b}, el LR “Todas
(a+b)*a(a+b)*a(a+b)*.

DEFINICIÓN: un Lenguaje Formal es un LR si existe una ER que lo represente.

A cada ER le corresponde un único LR. Sin embargo, un LR puede ser representado por varias ERs.
Afirmamos entonces: dos ERs son equivalentes si representan el mismo LR.

El LR: “Todas las palabras sobre el alfabeto {a,b} que tienen por lo menos una a y por lo menos una
b” puede ser representado por la siguiente ER: (a+b)*a(a+b)*b(a+b)* + (a+b)*b(a+b)*a(a+b)*.
O bien por esta otra ER: (a+b)*(a(a+b)*b+b(a+b)*a)(a+b)*.

OPERACIONES SOBRE LENGUAJES REGULARES

LA UNIÓN DE LENGUAJES REGULARES

Sean L1 y L2 dos LRs. Entonces L1  L2, es un LR Si L1 es representado por una ER R1 y L2 es
representado por cierta expresión R2, la unión L1  L2 es representada por la ER R1+R2.
Si L1 es representado por a*b y L2 es representado por la a+b*, L1  L2 es representado por a*b +
a+b*.

LA CONCATENACIÓN DE LENGUAJES REGULARES
La concatenación de dos LRs, L1L2 es un LR en el que cada palabra está formada por la
concatenación de una palabra de L1 con una palabra de L2. Por ende, la cardinalidad del LR
concatenación es el producto de las cardinalidades de los LRs de partida.

las palabras que contienen como mínimo dos aes”

la ER

3 Clase 3 SSL

Sea L1 = {ab, cd} y sea L2 = {aa, acc, ad}. Entonces: L1L2 = {abaa, abacc, abad, cdaa, cdacc, cdad} y
su cardinalidad es 6.
Si L1 es representado por una ER R1 y L2 es representado por R2, entonces la concatenación L1L2 es
representada por la ER R1R2.
Si L1 es representado por a*b y L2 por a+b*, L1L2 es representada por la ER a*b(a+b*).

LA CLAUSURA DE KLEENE DE UN LENGUAJE REGULAR
Si L es un LR, su clausura de Kleene, L*, es un LR infinito, en general formado por: la palabra vacía,
las palabras de L y todas aquellas palabras que se obtienen concatenando palabras de L, un número
arbitrario de veces. Ssalvo una excepción, esta se produce si el LR está formado solo por la palabra
vacía.
Sea L = {ab, ba}. Entonces, L* = {ε, ab, ba, abab, abba, baba, ababab, ababba, abbaba, bababa, …}.
Si L es representado por la ER R, L* es representado por R*.
Si L es representado por a*b, L* es representado por (a*b)*.

LA CLAUSURA POSITIVA DE UN LENGUAJE REGULAR
Si L es un LR, su clausura positiva, L+, es un LR formado por las palabras de L y todas aquellas
palabras que se obtienen concatenando palabras de L, un número arbitrario de veces. Si L es
representado por R, L+ es representado por R+. Si L es representado por a*b, L+ es representado por
(a*b)+. La clausura positiva de un LR contiene a la palabra vacía solo si ésta pertenece al lenguaje
original.

EL COMPLEMENTO DE UN LENGUAJE REGULAR
El complemento de un LR con respecto al Lenguaje Universal, Lc, es un LR que está formado por
todas aquellas palabras que no pertenecen al lenguaje original.
Si L es representado por la ER (a+b)+, Lc solo contiene a la palabra vacía.
Si L es a(a+b)* entonces Lc es b(a+b)* + .
No existen operadores oficiales para describir el complemento de una ER

LA INTERSECCIÓN DE DOS LENGUAJES REGULARES
La intersección de dos LRs es un LR constituido por todas aquellas palabras que pertenecen a los dos
lenguajes dados.
Sea el alfabeto {a,b}. Si L1 es a(a+b)* [todas las palabras que comienzan con a] y L2 es (a+b)*b [todas
las palabras que terminan con b], entonces L1  L2 es a(a+b)*b [todas las palabras que comienzan
con a y terminan con b].
No existen operadores para describir la intersección de dos ERs.

EXPRESIONES REGULARES Y LENGUAJES DE PROGRAMACIÓN
IDENTIFICADOR puede representarse mediante la ER L(L+D)*.
CONSTANTE REAL ER D+.D*.
Sea un LP que solo tiene tres PALABRAS RESERVADAS: if, else y while. ER if+else+while.

DEFINICIÓN FORMAL DE LAS EXPRESIONES REGULARES
operadores básicos unión (+), concatenación () y clausura de Kleene (*), y se definen formalmente
de la siguiente manera recursiva:
ø es una ER que representa al LR vacío (sin palabras).
 es una ER que representa al LR que solo contiene la palabra vacía: {}.
Todo símbolo x de un alfabeto corresponde a una ER x que representa a un LR que solo tiene una
palabra con ese símbolo x.

4 Clase 3 SSL

Una cadena s es una ER s que representa a un LR que solo contiene la palabra s. .
Si R1 y R2 son ERs, entonces R1 + R2 es ER
Si R1 y R2 son ERs, entonces R1  R2 es ER
Si R1 es una ER, entonces R1* es una ER.
Si R1 es una ER, entonces (R1) es una ER. .

Si R1 es una ER, entonces R1+ es una ER.
Si R1 es una ER, entonces R1n (con n  0 y entero) es una ER.

Con respecto a la precedencia de los operadores, ya se ha informado que:

1. Los operadores “clausura de Kleene”, “clausura positiva” y “potencia” tienen prioridad

máxima;

2. El operador “concatenación” tiene prioridad media; y
3. El operador “unión” tiene prioridad mínima.



5 Clase 3 SSL

EXPRESIONES REGULARES EXTENDIDAS

Metacaracteres Explicación y Ejemplo
. (punto)

(barra

|
vertical)
[ ] (corchetes)

[]

{ } (llaves)

{,}

?



+

( )

Se corresponde con cualquier carácter, excepto el “fin de línea” (\n). Ejemplo: a.a
es cualquier cadena de tres caracteres en la que el primer y el tercer caracteres
son a
Operador unión de ERs. Ejemplo: ab|b representa la ER ab+b

Clase de caracteres. Ejemplo: [abx] representa la ER a+b+x

Clase de caracteres en un intervalo. Ejemplo 1: [ad] representa la ER a+b+c+d.
Ejemplo 2:
[0-9 a-z] representa a cualquier dígito decimal o cualquier letra minúscula (del
alfabeto inglés)
Operador potencia, repetición determinada del patrón que lo precede como
operando.
Ejemplo 1: a{3} representa la ER aaa. Ejemplo 2: (ab){4} = abababab
Operador potencia extendido a un intervalo. Ejemplo: a{1,3} representa la ER
a+aa+aaa

Cero o una ocurrencia de la ER que lo precede. Ejemplo: a? representa la ER a+

Operador clausura de Kleene, cero o más ocurrencias de la ER que lo precede.
Ejemplo: a representa la ER a*
Operador clausura positiva, una o más ocurrencias de l