Upload
vuonghanh
View
240
Download
0
Embed Size (px)
Citation preview
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Tema 5: Expresiones Regulares
U.D. Computacion
DSIC - UPV
3 de marzo de 2011
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 1 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Indice
Definiciones
Propiedades
Construcciones sobre expresiones regulares
Sıntesis de automatas finitos
Analisis de automatas finitos
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 2 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Definiciones
Inductivamente, una expresion regular sobre Σ se define:
∅ denota el lenguaje vacioλ denota el lenguaje {λ}∀a ∈ Σ, a denota 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 LrLs
(r)∗ denota el lenguaje L∗r
Solo son expresiones regulares las construidas de esta forma
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 3 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Propiedades
Sean α, β y γ expresiones regulares
1 α + (β + γ) = (α + β) + γ2 α(βγ) = (αβ)γ3 α + β = β + α4 α(β + γ) = (αβ) + (αγ)5 (α + β)γ = (αγ) + (βγ)6 αλ = λα = α7 α + ∅ = ∅ + α = α8 α∅ = ∅α = ∅9 λ∗ = λ10 ∅∗ = λ11 α∗ = λ + αα∗
12 (α∗ + β∗)∗ = (α∗β∗)∗ = (α + β)∗
13 (αβ)∗α = α(βα)∗
14 (α∗β)∗α∗ = (α + β)∗
15 (α∗β)∗ = (α + β)∗β + λ
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 4 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Construcciones
Homomorfismo
Reverso
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 5 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Construcciones
HomomorfismoDada una expresion regular α y un homomorfismoh : Σα → ∆, para obtener una expresion regular parah(L(α)), basta sustituir cada sımbolo a de α por h(a)
Por ejemplo, considerando α = a(bb∗ + (aa)∗)∗b y elhomomorfismo: h(a) = 0 y h(b) = 11, la expresion regularpara h(L(α)) serıa:
0(11(11)∗ + (00)∗)∗11
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 6 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Construcciones
ReversoDada una expresion regular α, para obtener una expresionregular αr tal que L(αr ) = (L(α))r , aplicamosrecursivamente las siguientes reglas:
Si α = ∅, α = λ o α = a ∈ Σ, entonces αr = αSi α = β + γ, entonces αr = βr + γr
Si α = βγ, entonces αr = γrβr
Si α = β∗, entonces αr = (βr )∗
Por ejemplo, considerando α = a(b(a + b)∗ + (bba)∗)∗b,la expresion regular para (L(α))r serıa:
αr = b((a + b)∗b + (abb)∗)∗a
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 7 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Sıntesis de AFs a partir de ERs
Algoritmo de Brzozowski
Automata de Posicion
Automata Follow
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 8 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Calculo de Derivadas
Reglas para el calculo de las derivadasRespecto a sımbolos (a, b ∈ Σ, r , s E.R.)
1 a−1∅ = ∅
2 a−1
λ = ∅
3 a−1
b =
(
∅ si a 6= b
λ si a = b
4 a−1(r + s) = a
−1r + a
−1s
5 a−1(rs) =
(
(a−1r)s si λ 6∈ r
(a−1r)s + a
−1s si λ ∈ r
6 a−1
r∗ = (a−1
r)r∗
Respecto a cadenas (a ∈ Σ, x ∈ Σ∗)
1 λ−1
r = r
2 (xa)−1r = a
−1(x−1r)
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 9 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Algoritmo de Brzozowski
Entrada: α expresion regular sobre ΣSalida: AFD mınimo para L(α)Metodo:
Q = {α}; q0 = α; F = ∅; δ = ∅;if λ ∈ L(α) then
F = F ∪ {α}end if
activos = {α}while activos 6= {} do
β = First(activos)activos = Rest(activos)for all a ∈ Σ do
β′ = a−1β
if 6 ∃r ∈ Q : L(r) = L(β′) then
Q = Q ∪ {β′}δ = δ ∪ {(β, a, β′)}activos = activos ∪ {β′}if λ ∈ L(β′) then
F = F ∪ {β′}end if
end if
end for
end while
Return (Q, Σ, δ, q0, F )Fin Metodo
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 10 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Algoritmo de Brzozowski. Ejemplo
Consideremos α = (a + b)∗bb(a + b)∗:
q0 = α = (a+b)∗bb(a+b)∗; λ 6∈ L(q0) por lo tanto F = ∅a−1q0 = q0
b−1q0 = (a + b)∗bb(a + b)∗ + b(a + b)∗ = q1; λ 6∈ L(q1)por lo tanto F = ∅.a−1q1 = q0
b−1q1 = (a + b)∗bb(a + b)∗ + b(a + b)∗ + (a + b)∗ =(a + b)∗ = q2; λ ∈ L(q2) por lo tanto F = {q2}.a−1q2 = b−1q2 = q2
a
b
b
a
a,b
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 11 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata de Posicion
Automata local. Lenguaje Local
Expresion regular linearizada
AFD para una expresion regular linearizada
Automata de posicion
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 12 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata local. Lenguaje Local
El AFD A = (Q,Σ, δ, q0,F ) es local si y solo si paracualquier a ∈ Σ el conjunto {δ(q, a) : q ∈ Q} posee a losumo un elemento
Si ademas no existe ningun arco que alcance q0, elautomata es local estandar
Un lenguaje es local si y solo si es reconocido por unautomata local estandar
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 13 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Expresion regular linearizada
Sea α una expresion regular y sea n el numero de sımbolosen α excluyendo parentesis y sımbolos de operacion. Laexpresion linearizada de α (denotada por α) se obtienecolocando un subındice j ∈ {1, . . . , n} a cada sımbolo deα indicando su posicion.p.e.: Siendo
α = (a + b)(a∗ + ba∗ + b∗)∗
la version linearizada es
α = (a1 + b2)(a∗
3 + b4a∗
5 + b∗
6)∗
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 14 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Expresion regular linearizada
Si Σα y Σα son los alfabetos de α y α respectivamente, yh : Σ∗
α → Σ∗
α es un homomorfismo que borra lossubındices, entonces:
h(L(α)) = L(α)
Por lo tanto, puede obtenerse un automata finito paraL(α) construyendo un automata para L(α) yposteriormente eliminando los subındices de este automata(automata de posicion)
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 15 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Toda expresion regular linearizada denota un lenguajelocal (reconocido por un AF local estandar)Puede verse por induccion sobre la estructura de lasexpresiones regulares.
Casos base:
λ ∅
a
a
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 16 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Expresiones compuestas:Sean α y β expresiones regulares linearizadas, y seanA(α) = (Q1,Σ1, δ1, q1,F1) y A(β) = (Q2,Σ2, δ2, q2,F2),con Σ1 ∩ Σ2 = ∅, automatas locales que aceptan L(α) yL(β) respectivamente:
q1
a1
an
......
(α)
q2
b1
bm
......
(β)
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 17 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Union (α + β):
Q = (Q1 − {q1}) ∪ (Q2 − {q2}) ∪ {q0}, q0 /∈ Q1 ∪ Q2.δ = {(q, a, q′) ∈ δ1 ∪ δ2 : q /∈ {q1, q2}} ∪ {(q0, a, q) :(q1, a, q) ∈ δ1 ∨ (q2, a, q) ∈ δ2},
F =
{
F1 ∪ F2 si q1 /∈ F1 ∧ q2 /∈ F2
(F1 − {q1}) ∪ (F2 − {q2}) ∪ {q0} en otro caso.
q1
a1
an
......
q2
b1
bm
......
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 18 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Union (α + β):
Q = (Q1 − {q1}) ∪ (Q2 − {q2}) ∪ {q0}, q0 /∈ Q1 ∪ Q2.δ = {(q, a, q′) ∈ δ1 ∪ δ2 : q /∈ {q1, q2}} ∪ {(q0, a, q) :(q1, a, q) ∈ δ1 ∨ (q2, a, q) ∈ δ2},
F =
{
F1 ∪ F2 si q1 /∈ F1 ∧ q2 /∈ F2
(F1 − {q1}) ∪ (F2 − {q2}) ∪ {q0} en otro caso.
q0
q1
a1
an
......
q2
b1
bm
......
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 19 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Union (α + β):
Q = (Q1 − {q1}) ∪ (Q2 − {q2}) ∪ {q0}, q0 /∈ Q1 ∪ Q2.δ = {(q, a, q′) ∈ δ1 ∪ δ2 : q /∈ {q1, q2}} ∪ {(q0, a, q) :(q1, a, q) ∈ δ1 ∨ (q2, a, q) ∈ δ2},
F =
{
F1 ∪ F2 si q1 /∈ F1 ∧ q2 /∈ F2
(F1 − {q1}) ∪ (F2 − {q2}) ∪ {q0} en otro caso.
q0
......
......
a1
an
b1
bm
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 20 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Producto (α · β) (q2 6∈ F2):
Q = (Q1 ∪ Q2) − {q2}),δ = δ1 ∪ {(q, a, q′) ∈ δ2 : q 6= q2} ∪ {(q, a, q′) : q ∈F1 ∧ (q2, a, q
′) ∈ δ2},q0 = q1
F = F2
q1
a1
an
......
q2
b1
bm
......
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 21 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Producto (α · β) (q2 6∈ F2):
Q = (Q1 ∪ Q2) − {q2}),δ = δ1 ∪ {(q, a, q′) ∈ δ2 : q 6= q2} ∪ {(q, a, q′) : q ∈F1 ∧ (q2, a, q
′) ∈ δ2},q0 = q1
F = F2
q1
a1
an
......
q2
b1
bm
......
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 22 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Producto (α · β) (q2 6∈ F2):
Q = (Q1 ∪ Q2) − {q2}),δ = δ1 ∪ {(q, a, q′) ∈ δ2 : q 6= q2} ∪ {(q, a, q′) : q ∈F1 ∧ (q2, a, q
′) ∈ δ2},q0 = q1
F = F2
q1
a1
an
......
......
b1
bmb1bm
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 23 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Producto (α · β) (q2 ∈ F2):
Q = (Q1 ∪ Q2) − {q2}),δ = δ1 ∪ {(q, a, q′) ∈ δ2 : q 6= q2} ∪ {(q, a, q′) : q ∈F1 ∧ (q2, a, q
′) ∈ δ2},q0 = q1
F = F1 ∪ (F2 − {q2})
q1
a1
an
......
q2
b1
bm
......
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 24 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Producto (α · β) (q2 ∈ F2):
Q = (Q1 ∪ Q2) − {q2}),δ = δ1 ∪ {(q, a, q′) ∈ δ2 : q 6= q2} ∪ {(q, a, q′) : q ∈F1 ∧ (q2, a, q
′) ∈ δ2},q0 = q1
F = F1 ∪ (F2 − {q2})
q1
a1
an
......
q2
b1
bm
......
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 25 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Producto (α · β) (q2 ∈ F2):
Q = (Q1 ∪ Q2) − {q2}),δ = δ1 ∪ {(q, a, q′) ∈ δ2 : q 6= q2} ∪ {(q, a, q′) : q ∈F1 ∧ (q2, a, q
′) ∈ δ2},q0 = q1
F = F1 ∪ (F2 − {q2})
q1
a1
an
......
......
b1
bmb1bm
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 26 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Clausura (α∗):
δ′ = δ ∪ {(q, a, q′) : q ∈ F ∧ (q0, a, q′) ∈ δ}
F = F1 ∪ {q1})
q1
a1
an
......
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 27 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada
Clausura (α∗):
δ′ = δ ∪ {(q, a, q′) : q ∈ F ∧ (q0, a, q′) ∈ δ}
F = F1 ∪ {q1})
q1
a1
an
......
an
a1
a1
an
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 28 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
AFD para una expresion regular linearizada.
Ejemplo
Sea α = (a + b)(a∗ + ba∗ + b∗)∗. Entoncesα = (a1 + b2)(a
∗
3 + b4a∗
5 + b∗
6)∗
a1
b2
a1 + b2
a3
a3
a∗3
b4 a5
a5
b4a∗
5
b4 a5
a5a3
b6
a3
b6
a∗3 + b4a∗
5 + b6
b4a5
a5
a3
b6
a3
b6
(a∗3 + b4a∗
5 + b6)∗
a3
a3
a3
b4
b4
b4b4
b6
b6
b6
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 29 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata de posicion. Algoritmo
1: Entrada: α expresion regular sobre Σ2: Salida: AFD para L(α)3: Metodo:
4: Obtener α version linearizada de α5: Obtener A un Automata local estandar para α6: Apos = h(A), donde h es un homomorfismo de borrado de
los subındices.7: Return Apos
8: Fin Metodo
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 30 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata de posicion. Ejemplo
Dada α = (a + b)(a∗ + ba∗ + b∗)∗ y su version linearizadaα = (a1 + b2)(a
∗
3 + b4a∗
5 + b∗
6)∗, el automata local estandar
para α es:
a1
b2
a3
b4b6
a3 b4
b6
a3
b4
b6a3
b4
b6
a3
b4
a5
b6
a3
a5
b4
b6
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 31 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata de Posicion. Ejemplo
y el automata de posicion para α = (a + b)(a∗ + ba∗ + b∗)∗ es:
a
b
a
bb
a b
b
a
b
ba
b
b
a
b
a
b
a
a
b
b
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 32 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata Follow
Relacion follow
Automata follow
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 33 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata Follow
El automata follow de una expresion regular α se proponecomo el automata cociente del automata de posicion porla siguiente relacion:
p ≡f q ⇔
{
p, q ∈ F o bien p, q ∈ Q − F
follow(p) = follow(q)
donde follow(p) = {q ∈ Q : ∃a ∈ Σ, δ(p, a) = q}
El automata cociente resultante es una reduccion parcialdel automata de posicion.
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 34 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata Follow
Recordamos el automata de posicion paraα = (a + b)(a∗ + ba∗ + b∗)∗:
q0
q1
q2
q3
q6
q4 q5
a
b
a
bb
a b
b
a
b
ba
b
b
a
b
a
b
a
a
b
b
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 35 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Automata Follow
Las clases de equivalencia son: {q0}, {q1, q2, q3, q6}, {q4, q5},con lo que el automata follow para α queda:
{q0} {q1, q2, q3, q6} {q4, q5}a, b
a, b a, b
b
a, b
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 36 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Analisis de automatas finitos
Sistemas de ecuaciones en expresiones regulares
Lema de Arden
Analisis de automatas finitos
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 37 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Sistemas de ecuaciones en expresiones regulares.
Lema de Arden
Ecuacion en expresiones regulares: Ecuacion lineal dondevariables y coeficientes toman la forma de expresionesregulares.
X = rX + s
Lema de Arden: Sea X = rX + s una ecuacion enexpresiones regulares. X = r∗s es una solucion para laecuacion. Es unica si λ 6∈ r
demostramos que r∗s es solucion:
rX + s =X=r∗s
rr∗s + s = (rr∗ + λ)s =rr∗+λ=r∗
r∗s
Si λ ∈ r existen infinitas soluciones: ∀t ⊆ Σ∗, r∗(s + t) essolucion:
X =rX + s = rr∗(s + t) + s = rr∗s + rr∗t + s =
=(rr∗ + λ)s + rr∗t =rr∗+λ=r∗
r∗s + r∗t =X=r∗(s+t)
X
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 38 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Sistemas de ecuaciones en expresiones regulares
Dado un sistema de ecuaciones en expresiones regulares:
X1 = r11X1 + r12X2+ . . . + r1nXn + s1X2 = r11X1 + r12X2+ . . . + r1nXn + s2
. . .Xn = r11X1 + r12X2+ . . . + r1nXn + s3
la resolucion viene tras aplicar el metodo de Gaussutilizando el Lemma de Arden para reducir.
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 39 / 40
Tema 5:
Expresiones
Regulares
U.D.Computacion
Definiciones
Propiedades
Construcciones
Sıntesis deAFs a partirde ERs
Algoritmo deBrzozowski
Automata deposicion
AutomataFollow
Analisis deAFs. Lema deArden
Analisis de AFs. Algoritmo
1: Entrada: Automata finito A = (Q,Σ, δ, q1,F ) conQ = {q1, q2, . . . , qn}
2: Salida: Expresion regular para L(A)3: Metodo:
4: Por cada estado qi introducir una variable Xi
5: Si qi ∈ F entonces en la parte derecha de la i -esimaecuacion aparece el termino λ
6: Si qj ∈ δ(qi , a) entonces en la parte derecha de la i -esimaecuacion aparece el termino aXj , con a ∈ Σ ∪ {λ}
7: Resolver el sistema de ecuaciones en expresiones regularesutilizando el Lema de Arden para reducir
8: Devolver la expresion regular asociada al estado inicial9: Fin Metodo
U.D. Computacion (DSIC - UPV) Tema 5: Expresiones Regulares 3 de marzo de 2011 40 / 40