Herramientas Computacionales Ligadas A Los Lenguajes

Las expresiones regulares se usan para representar los posibles lenguajes que pueden ser generados a partir de un determinado alfabeto, existen varias reglas y operaciones que se pueden hacer con las expresiones regulares, los analizaremos a continuació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:

1. ()

2. * cierre

3. . concatenación

4. + unión

Ejemplo:

Algunos ejemplos de expresión regular son:

(0 + 1)*01 (aa + ab + ba + bb)* a*(a + b) (aa)*(bb)

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.

Operaciones de los lenguajes:

1 Unión: Si L y M son dos lenguajes, su unión se denota por L ∪ M

2 Concatenación: La concatenación es: LM o L.M

3 Cerradura (o cerradura de Kleene): Si L es un lenguaje su cerradura se denota por: L∗.

Si E es una expresión regular, entonces L(E) denota el lenguaje que define E.

Las expresiones se construyen de la manera siguiente:

1 Las constantes ǫ y ∅ son expresiones regulares que representan a los lenguaje L(ǫ) = {ǫ} y L(∅) = ∅ respectivamente

2 Si a es un símbolo, entonces es una expresión regular que representan al lenguaje: L(a) = {a}

Operandos

Si E y F son expresiones regulares, entonces E + F también lo es denotando la unión de L(E) y L(F).

L(E + F) = L(E) ∪ L(F).

2 Si E y F son expresiones regulares, entonces EF también lo es denotando la concatenación de L(E) y L(F). L(EF) = L(E)L(F).

3 Si E es una expresión regular, entonces E∗ también lo es y denota la cerradura de L(E). Osea L(E∗) = (L(E))∗

4 Si E es una expresión regular, entonces (E) también lo es. Formalmente: L((E)) = L(E).

Con las expresiones regulares se representan patrones de cadenas de caracteres. Una ER r se encuentra completamente definida mediante

...