Expresiones regular

esTema 3: Expresiones regulares
´ ´ Departamento de Sistemas Informaticos y Computacion

DSIC - UPV

http://www.dsic.upv.es

– p.1/14

Tema 3: Expresiones regulares
• Definiciones ypropiedades • Obtención de AFD a partir de expresiones regulares ◦ Reglas para el cálculo de las derivadas ◦ Método de las derivadas • Sistemas de ecuaciones en ER • Sistemas de ecuaciones asociados aautómatas finitos

DSIC - UPV

http://www.dsic.upv.es

– p.2/14

Relaciones entre formalismos

AFD

AFN

AFλ

Gramaticas lineales (por la derecha)

Expresiones regulares
DSIC - UPVhttp://www.dsic.upv.es

– p.3/14

Expresiones Regulares. Definicion
• Inductivamente, una expresión regular sobre Σ se define: ◦ ∅ denota el lenguaje vacio ◦ λ denota el lenguaje {λ} ◦ ∀a ∈ Σ, adenota el lenguaje {a} ◦ Si r y s son expresiones regulares que denotan Lr y Ls : • (r) denota el lenguaje Lr • r + s denota el lenguaje Lr ∪ Ls • rs denota el lenguaje Lr Ls • (r)∗ denota el lenguaje L∗ r◦ Sólo son expresiones regulares las construidas de esta forma  ()   ∗ • Prioridad de operadores: Concatenación    Unión

DSIC - UPV

http://www.dsic.upv.es

– p.4/14

ExpresionesRegulares. Propiedades
• Sean α, β y γ expresiones regulares 1. α + (β + γ) = (α + β) + γ α(βγ) = (αβ)γ 2. α + β = β + α 3. α(β + γ) = (αβ) + (αγ) (α + β)γ = (αγ) + (βγ) 4. αλ = λα = α 5. α + ∅ = ∅ +α = α α∅ = ∅α = ∅ 6. λ∗ = λ 7. ∅∗ = λ 8. α∗ = λ + αα∗ 9. (α∗ + β ∗ )∗ = (α∗ β ∗ )∗ = (α + β)∗ 10. (αβ)∗ α = α(βα)∗ 11. (α∗ β)∗ α∗ = (α + β)∗ 12. (α∗ β)∗ = (α + β)∗ β + λ

DSIC - UPVhttp://www.dsic.upv.es

– p.5/14

´ Obtencion de AFD a partir de expresiones regulares
• Reglas para el cálculo de las derivadas ◦ Respecto a símbolos (a, b ∈ Σ, r, s E.R.) 1. a−1 ∅ = ∅ 2. a−1 λ = ∅ 3. a−1 a= λ; a−1 b = ∅ si (a = b) 4. a−1 (r + s) = a−1 r + a−1 s 5. a−1 (rs) = (a−1 r)s si λ ∈ r (a−1 r)s + a−1 s si λ ∈ r x ∈ Σ∗ )

6. a−1 r ∗ = (a−1 r)r ∗ ◦ Respecto a cadenas (a ∈ Σ, 1. λ−1 r = r 2....