Expresiones Regulares Unidad 2

Concepto de Expresión Regular

El objetivo de las expresiones regulares es representar todos los posibles lenguajes definidos sobre un alfabeto Σ, en base a una serie de lenguajes primitivos, y unos operadores de composición.

 Lenguajes primitivos: el lenguaje vacío, el lenguaje formado por la palabra vacía, y los lenguajes correspondientes a los distintos símbolos del alfabeto.

Operadores de composición: la unión, la concatenación y el cierre.

Ejemplo:

    1.  Lenguaje formado por las cadenas que terminan en 01:
         {0,1}*.{01}=
         ({0}∪{1})*.{01}
         ⇒ Expresión regular: (0+1)*01

    2. Lenguaje formado por palabras de longitud par sobre a’s y b’s:
        {aa,ab,ba,bb}*=
        ({aa}∪{ab}∪{ba}∪{bb})*
        ⇒Expresión: (aa+ab+ba+bb)*

Definición 

Dado un alfabeto Σ, las expresiones regulares sobre Σ se definen de forma recursiva por las siguientes reglas:

     1. Las siguientes expresiones son expresiones regulares primitivas:

• ∅
• λ
• a, siendo a∈Σ.

     2.  Sean α y β expresiones regulares, entonces son expresiones regulares derivadas:

• α+β (unión)
• α.β (o simplemente αβ) (concatenación)
• α* (cierre)
• (α)

     3. No hay más expresiones regulares sobre Σ que las construidas mediante estas reglas.

Precedencia de los operadores:

• ()
• * cierre 
• . concatenación
• + unión

Lenguaje descrito por una ER 

Definición (Lenguaje descrito por una ER): 

Sea r una expresión regular sobre Σ. El lenguaje descrito por r, L(r), se define recursivamente de la siguiente forma:

     1. Si r=∅ ⇒ L(∅)= ∅

     2. Si r=λ ⇒ L(λ)= {λ}

     3. Si R=a, a∈Σ ⇒ L(a)= {a}

     4. Si R=α+β ⇒ L(α+β)= L(α)∪L(β)

     5. Si R=α.β ⇒ L(α.β)= L(α)L(β)

     6. Si R=α* ⇒ L(α*)= L(α)*

     7. Si R=(α) ⇒ L((α))= L(α)

donde α y β son expresiones regulares.

 Propiedades de Expresiones Regulares

Definición (equivalencia de ER): 

Dos expresiones regulares r1 y r2 se dicen equivalentes, r1 = r2, si describen el mismo lenguaje, esto es, si L(r1)=L(r2).

En base a esta definición se pueden establecer las siguientes equivalencias y propiedades:

 Respecto a las operaciones + y . :

     1. + y . son asociativas: α+(β+γ)=(α+β)+γ=α+β+γ y α.(β.γ)=(α.β).γ=α.β.γ

     2. + es conmutativa e idempotente: α+β=β+α y α+α=α

     3. Distributividad: α.(β+γ)=α.β+α.γ y (α+β).γ=α.γ+β.γ

     4. Elemento neutro: α.λ=λ.α=α y α+∅=∅+α=α

     5. ∅.α=α.∅=∅

     6. Si λ∈L(α), entonces α+λ=α

Respecto a la operación *:

     7. α*=λ+α.α*

     8. λ*=λ

     9. ∅*=λ

     10. α*.α*=α*

     11. α.α*=α*.α

     12. (α*)*=α*

     13. (α*+β*)*=(α*.β*)*=(α+β)*=(α*.β)*.α*

     14. (α.β)*.α=α.(β.α)*

Para comprobar si dos expresiones son equivalentes se puede intentar transformarlos mediante estas reglas en una misma expresión.