Propiedades de las expresiones regulares

Expresiones regulares :

• Es una forma de representar lenguajes regulares.
• La descripción algebraica de los lenguajes regulares se realiza mediante expresiones regulares.
• Pueden definir el mismo lenguaje que pueden describir varias formas de autómatas finitos.
• Las expresiones regulares ofrecen algo que los autómatas finitos no ofrecen, es decir, es una forma declarativa de expresar las strings que queremos aceptar. Actúan como entrada para muchos sistemas. Se utilizan para la coincidencia de strings en muchos sistemas (Java, python, etc.)
• Por ejemplo, generadores de analizadores léxicos, como Lex o Flex.

Los operadores ampliamente utilizados en las expresiones regulares son el cierre de Kleene (∗), la concatenación (.) y la unión (+).

Reglas para expresiones regulares:

• El conjunto de expresiones regulares se define mediante las siguientes reglas.
• Cada letra de ∑ se puede convertir en una expresión regular, string nula, ∈ en sí mismo es una expresión regular. 
  Si r1 y r2 son expresiones regulares, entonces (r1), r1.r2, r1+r2, r1*, r1 ⁺ también son expresiones regulares.

Ejemplo:   ∑ = {a, b} y r es una expresión regular del lenguaje hecha con estos símbolos 

Lenguaje habitual	conjunto regular
∅	{ }
∈	{∈}
a*	{∈, a, aa, aaa…..}
a+b	{una, b}
abdominales	{ab}
a* + ba	{∈, un, aa, aaa,……, ba}

Operaciones realizadas en expresiones regulares:
1. Unión:
la unión de dos lenguajes regulares, L1 y L2, que se representan usando L1 ∪ L2, también es regular y representa el conjunto de strings que están en L1 o L2 o en ambos.
Ejemplo
L1 = (1+0).(1+0) = {00 , 10, 11, 01} y 
L2 = {∈ , 100}
luego L1 ∪ L2 = {∈, 00, 10, 11, 01, 100} .

2. Concatenación:
la concatenación de dos idiomas regulares, L1 y L2, que se representan mediante L1. L2 también es regular y representa el conjunto de strings que se forman al tomar cualquier string en L1 y concatenarla con cualquier string en L2.
Ejemplo:
L1 = { 0,1 } y L2 = { 00, 11} luego L1.L2 = {000, 011, 100, 111}.

3. Cierre de Kleene :
si L1 es un lenguaje regular, entonces el cierre de Kleene, es decir, L1* de L1, también es regular y representa el conjunto de esas strings que se forman al tomar un número de strings de L1 y la misma string se puede repetir cualquier número de veces y concatenando esas strings.
Ejemplo: 
L1 = { 0,1} = {∈, 0, 1, 00, 01, 10, 11 …….} , entonces L* son todas las strings posibles con los símbolos 0 y 1, incluida una string nula .

Propiedades algebraicas de las expresiones regulares: el
cierre de Kleene es un operador unario y el operador de unión (+) y concatenación (.) son operadores binarios.

1. Cierre:
si r1 y r2 son expresiones regulares (RE), entonces 

• r1* es un RE
• r1+r2 es un RE
• r1.r2 es un RE

2. Leyes de cierre –

• (r*)* = r, cerrar una expresión que ya está cerrada no cambia el idioma.
• ∅* = ∈, una string formada al concatenar cualquier número de copias de una string vacía está vacía.
• r ⁺ = rr* = r*r, como r* = ∈ + r + rr+ rrr …. y rr* = r+ rr + rrr ……
• r* = r*+ ∈

3. Asociatividad:
si r1, r2, r3 son RE, entonces 
i.) r1+ (r2+r3) = (r1+r2) +r3 

• Por ejemplo : r1 = a, r2 = b, r3 = c, entonces
• La expresión regular resultante en LHS se convierte en a+(b+ c) y el conjunto regular para el RE correspondiente es {a, b, c}.
• porque el RE en RHS se convierte en (a+ b) + c y el conjunto regular para este RE es {a, b, c}, que es el mismo en ambos casos. Por lo tanto, la propiedad de asociatividad se cumple para el operador de unión.

ii.) r1.(r2.r3) = (r1.r2).r3

• Por ejemplo – r1 = a , r2 = b , r3 = c
• Entonces la string aceptada por RE a.(bc) es solo abc.
• La string aceptada por RE en RHS es (ab).c es solo abc, que es igual en ambos casos. Por lo tanto, la propiedad de asociatividad se cumple para el operador de concatenación.

La propiedad de asociatividad no se cumple para el cierre de Kleene (*) porque es un operador unario.

4. Identidad –
En el caso de operadores de unión
si r+ x = r ⇒ x= ∅ como r ∪ ∅= r, entonces ∅ es la identidad de +.
Por lo tanto, ∅ es el elemento de identidad para un operador de unión.
En el caso del operador de concatenación,
si rx = r, para x= ∈
r.∈ = r ⇒ ∈ es el elemento de identidad para el operador de concatenación (.) . 

5. Aniquilador –

• Si r+ x = r ⇒ r ∪ x= x , no hay aniquilador para +
• En el caso de un operador de concatenación, rx = x, cuando x = ∅, entonces r.∅ = ∅, por lo tanto, ∅ es el aniquilador del operador (.). Por ejemplo {a, aa, ab}.{ } = { }

6. Propiedad conmutativa:
si r1, r2 son RE, entonces 

• r1+r2 = r2+r1. Por ejemplo, para r1 =a y r2 =b, entonces RE a+ b y b+ a son iguales.
• r1.r2 ≠ r2.r1. Por ejemplo, para r1 = a y r2 = b, entonces RE ab no es igual a ba

7. Propiedad distribuida:
si r1, r2, r3 son expresiones regulares, entonces 

• (r1+r2).r3 = r1.r3 + r2.r3 es decir, distribución correcta
• r1.(r2+ r3) = r1.r2 + r1.r3 es decir, distribución izquierda
• (r1.r2) +r3 ≠ (r1+r3)(r2+r3)

8. Ley idempotente –

• r1 + r1 = r1 ⇒ r1 ∪ r1 = r1 , por lo tanto, el operador de unión satisface la propiedad idempotente.
• El operador de concatenación rr ≠ r ⇒ no satisface la propiedad idempotente.

9. Identidades para la expresión regular:
hay muchas identidades para la expresión regular. Sean p, q y r expresiones regulares.

• ∅ + r = r
• ∅.r= r.∅ = ∅
• ∈.r = r.∈ =r
• ∈* = ∈ y ∅* = ∈
• r + r = r
• r*.r* = r*
• rr* = r*.r = r ⁺ .
• (r*)* = r*
• ∈ +rr* = r* = ∈ + rr*
• (pq)*.p = p.(qp)*
• (p + q)* = (p*.q*)* = (p* + q*)*
• (p+ q).r= p.r+ qr y r.(p+q) = rp + rq