Unidad 2 2.1Definición formal de una ER.

Expresiones y gram´aticas regulares

Definicio´n de expresio´n regular

Una expresio´n regular es una notacio´n normalizada para representar lenguajes regulares, es decir, lenguajes generados por gram´aticas de tipo 3. Como veremos, las expresiones regulares permiten describir con exactitud y sencillez cualquier lenguaje regular. Para definir una expresio´n regular(e.r.) se pueden utilizar todos los s´ımbolos del alfabeto Σ y, adem´as, λ y Ø. Los operadores que tambi´en se pueden utilizar son:

+ representa la uni´on

. representa la concatenacio´n (este s´ımbolo no se suele escribir)

* representa el cierre de Kleene

( ) modifican las prioridades de los dema´s operadores

Una expresio´n regular se puede definir de acuerdo a los siguientes criterios:

1. Ø es una e.r. que representa al lenguaje vac´ıo (no tiene palabras) LØ = Ø

2. λ es una e.r. que representa al lenguaje Lλ = {λ}

3. a ∈ Σ es una e.r. que representa al lenguaje La = {a}

4. Si α y β son e.r. entonces α+ β tambi´en lo es y representa al lenguaje Lα+β = Lα ∪ Lβ

5. Si α y β son e.r. entonces αβ tambi´en lo es y representa al lenguaje Lαβ = LαLβ

6. Si α es una e.r. entonces α∗ tambi´en lo es y representa al lenguaje

S´olo son e.r. aquellas que puedan ser definidas utilizando los 6 puntos vistos ante-riormente.

La prioridad de las operaciones, que puede modificarse utilizando par´entesis, es de mayor a menor: ∗ . +

Ejemplos     Sea Σ = {0,1}

1. 01 + 001 es una e.r. que representa al lenguaje L = {01,001}

2. 0∗10∗ es una e.r. que representa a cualquier cadena binaria en la que hay un solo 1, L = {0n10m/n,m ≥ 0}

Sea Σ = {a,b,c}

3. a(a + b + c)∗ representa a cualquier cadena que empiece por a

4. (a + b + c)∗ representa al lenguaje universal definido sobre el alfabeto

´

          Algebra de las expresiones regulares

Propiedades de la unio´n (+)

1. Asociativa

2. Conmutativa

(α + β) + γ = α + (β + γ)

α + β = β + α

3. Elemento neutro (Ø)        α + Ø = α

4. Idempotencia            α + α = α

Propiedades de la concatenacio´n (.)

1. Asociativa           (αβ)γ = α(βγ)

2. Distributiva respecto de la unio´n           α(β + γ) = αβ + αγ

3. Elemento neutro (λ)        αλ = λα = α

4. αØ = Ø

5. No es conmutativa

Propiedades del cierre de Kleene (*)

1. λ∗ = λ

2. Ø∗ = λ

3. α∗α∗ = α∗

4. α∗α = αα∗

5. (α∗)∗ = α∗

6. α∗ = λ + αα∗

7. α∗ = λ + α + α2 + ... + αn + αn+1α∗

Σ

Si tenemos una funci´on f : En −→ EΣ (por ejemplo f(α,β) = α∗β), donde EΣ representa al conjunto de las expresiones regulares definidas sobre Σ, entonces:

8. f(α,β,γ,...) + (α + β + γ + ...)∗ = (α + β + γ + ...)∗

9. (f(α∗,β∗,γ∗,...))∗ = (α + β + γ + ...)∗

          Definicio´n de gram´atica regular

Como vimos en el tema anterior existen dos tipos de gram´aticas de tipo 3: las grama´ticas lineales por la derecha y las lineales por la izquierda.

Las producciones de las gram´aticas lineales por la derecha pueden ser de la forma:

1. A ::= a

2. A ::= aV

3. S ::= λ

donde A,V ∈ ΣN, a ∈ ΣT

y S es el s´ımbolo inicial de la gram´atica.

Las producciones de las gram´aticas lineales por la izquierda pueden ser de la

forma:

1. A ::= a

2. A ::= V a

3. S ::= λ

donde A,V ∈ ΣN, a ∈ ΣT

y S es el s´ımbolo inicial de la gram´atica.

Estos dos tipos de gram´aticas tienen el mismo poder generativo, es decir, dada una grama´tica lineal por la izquierda siempre existe una grama´tica lineal por la derecha que es equivalente a ella y viceversa. Adema´s, dado un lenguaje regular siempre existen, al menos, una gram´atica lineal por la izquierda y una grama´tica lineal por la derecha que lo generan.

Todo lenguaje de tipo 3 puede representarse mediante una e.r. y una e.r. siempre representa a un lenguaje de tipo 3.

          Ejemplos

Supongamos que Σ1 = {a,b,...,z}

1. El lenguaje L1 = {λ,a,aa,aaa,...} puede representarse con la e.r. a∗ y puede ser generado por la gr. lineal por la izquierda

P = {S ::= λ|Sa}

y por la gr. lineal por la derecha

P = {S ::= λ|aS}

2. El lenguaje de todas las palabras que empiezan por a puede representarse con

la e.r. a(a+b+...+ z)∗ y puede ser generado por la gr. lineal por la izquierda

y por la gr. lineal por la derecha

3. El lenguaje de las palabras que empiezan por a, terminan por c y adem´as de estas dos letras s´olo pueden tener b´s (tantas como se quieran) puede represen-tarse con la e.r. ab∗c y puede ser generado por la gr. lineal por la izquierda

y por la gr. lineal por la derecha

Los lenguajes regulares son especialmente adecuados para representar las carac-ter´ısticas l´exicas de un lenguaje de programaci´on, como veremos en los siguien-tes ejemplos en los que consideraremos un lenguaje de programaci´on similar a C.

4. Las cadenas que pueden ser consideradas como un identificador del lenguaje (nombres inventados por el programador para definir variables, funciones, etc.) esta´n formadas por letras (mayu´sculas y minu´sculas), d´ıgitos y el guio´n bajo ( ), pero no pueden comenzar por un d´ıgito. Este lenguaje definido sobre el alfabeto Σ2 = {a,...,z,A,...,Z,0,...,9, } se puede representar por la e.r.

(a + ...+ z + A + ... + Z + )(a + ...+ z + A + ... + Z + + 0 + ... + 9)∗

Esta e.r. representa palabras como Suma o Total1 pero no representar´ıa a 1Ab

Si trabajamos con el alfabeto Σ3 = {0,...,9,.,+ ,−,e,E} (el s´ımbolo de la suma + ha sido representado en un taman˜o menor del habitual para distinguirlo con claridad del operador unio´n (+))

5. La e.r. α = (0 + ... + 9)(0 + ... + 9)∗ permite representar a cualquier nu´mero natural (por ejemplo: 4, 27 o 256).

6. La e.r. β = α.(0 + ... + 9)∗ representa nu´meros reales no negativos con una notacio´n cl´asica (por ejemplo: 55.7, 854.95 o 5.).

7. La e.r. γ = (β(e + E)α) + (β(e + E)+α) + (β(e + E) − α) representa nu´meros reales no negativos con una notaci´on cient´ıfica (por ejemplo: 5.5e+10).