Story Transcript
Sentido de recorrido σ
... Cabeza de lectura
... γ Pila
q
i
Unidad de control de estados Componentes b´asicos de un aut´omata con pila.
Cinta
σ
i1
σi j
...
q
Z0
σ i j+1 ...
σi p
...
0
(a) σ
i1
...
σi j
σ i j+1 ...
σi p
...
γk 1
σ
i1
...
σi j
σ i j+1 ...
σi p
...
σ i j+1 ...
σi p
...
... γ km γ l2 ...
γ
l1 γl 2 ... q
γlq
q’
γlq
(b) σ
i1
...
σi j
(c) σ i j+1 ...
σi p
...
σ
i1
...
σi j
γ
h1 ...
γht
q
f
(d)
q
(e)
Fases de un aut´omata con pila: (a) configuraci´on inicial, (b) y (c) transici´on intermedia, (d) configuraci´on final por estado final y (e) configuraci´on final por pila vac´ıa.
Existen dos criterios para definir el lenguaje reconocido por un aut´omata con pila: El lenguaje que reconoce un aut´omata con pila P seg´ un el criterio de estado final se denota por “F (P )” y se define como: F (P ) = {x|x ∈ Σ∗ ∧ (q0 , x, Z0 ) ⊢∗ (qf , ǫ, α) ∧ qf ∈ F }
(1)
El lenguaje que reconoce un aut´omata con pila P seg´ un el criterio de la pila vac´ıa se denota por “V (P )” y se define como: V (P ) = {x|x ∈ Σ∗ ∧ (q0 , x, Z0 ) ⊢∗ (q, ǫ, ǫ)}
(2)
Consid´erese el aut´omata con pila P = (Q, Σ, Γ, δ, q0 , Z0 , F ) donde: Q = {q0 , q1 , q2 , q3 } F = {q3 } Σ = {a, b, c, $} Γ = {a, b, Z0 } y la funci´on de transici´on es (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)
q
(a, Z 0 , aZ0 ) 0
(b, Z0 , bZ0 )
δ(q0 , a, Z0) δ(q0 , b, Z0 ) δ(q1 , a, a) δ(q1 , a, b) δ(q1 , b, a) δ(q1 , b, b) δ(q1 , c, a) δ(q1 , c, b) δ(q2 , a, a) δ(q2 , b, b) δ(q2 , $, Z0)
q
= = = = = = = = = = =
(c, a, a) 1
(c, b, b)
q
($, Z 0 ,ε) 2
(a, a, ε) (b, b, ε)
(a, a, aa) (a, b, ab) (b, a, ba) (b, b, bb)
(q0 , abcba$, Z0 )
{(q1 , aZ0 )} {(q1 , bZ0 )} {(q1 , aa)} {(q1 , ab)} {(q1 , ba)} {(q1 , bb)} {(q2 , a)} {(q2 , b)} {(q2 , ǫ)} {(q2 , ǫ)} {(q3 , ǫ)}
⊢1 ⊢5 ⊢8 ⊢10 ⊢9 ⊢11
Como q3 ∈ F , la palabra abcba$ ∈ F (P ).
(q1 , bcba$, aZ0 ) (q1 , cba$, baZ0 ) (q2 , ba$, baZ0 ) (q2 , a$, aZ0 ) (q2 , $, Z0) (q3 , ǫ, ǫ)
q
3
Consid´erese un aut´omata con pila, que reconoce seg´ un el criterio de la pila vac´ıa, P = (Q, Σ, Γ, δ, q0 , Z0 , ∅) cuya funci´on de transici´on δ es: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
δ(q0 , 0, Z0 ) δ(q0 , 1, Z0 ) δ(q0 , 0, 0) δ(q0 , 0, 1) δ(q0 , 1, 0) δ(q0 , 1, 1) δ(q1 , 0, 0) δ(q1 , 1, 1) δ(q0 , ǫ, Z0 ) δ(q1 , ǫ, Z0 )
q
= = = = = = = = = =
{(q0 , 0Z0 )} {(q1 , 1Z0 )} {(q0 , 00), (q1 , ǫ)} {(q0 , 01)} {(q0 , 10)} {(q0 , 11), (q1 , ǫ)} {(q1 , ǫ)} {(q1 , ǫ)} {(q1 , ǫ)} {(q1 , ǫ)}
(0, 0, ε ) (1, 1, ε ) 0
(ε , Z ,ε )
q
1
0
(0, Z 0 , 0Z ) 0 (1, Z0 , 1Z0 ) (0, 0, 00) (0, 1, 01) (1, 0, 10) (1, 1, 11)
(0, 0,ε ) (1, 1, ε ) (ε , Z ,ε ) 0
V (P ) = {ww R|w ∈ L((0 + 1)∗ )}. Este lenguaje se denomina “pal´ındromo par”.
(q0 , 0110, Z0)
⊢1 ⊢5 ⊢6b ⊢7 ⊢10
(q0 , 110, 0Z0) (o ⊢9 (q0 , 0110, ǫ)) (q0 , 10, 10Z0) (q1 , 0, 0Z0 ) (o ⊢6a (q1 , 0, 110Z0)) (q1 , ǫ, Z0 ) (q1 , ǫ, ǫ)
Transformaci´ on de una aut´ omata con pila que utiliza el criterio del estado final en otro que utiliza el criterio de la pila vac´ıa. Dado P = (Q, Σ, Γ, δ, q0 , Z0 , F ) que reconoce por el criterio del estado final, se puede construir un aut´omata con pila P ′ equivalente que reconoce por el criterio de la pila vac´ıa. Se define P ′ = (Q′ , Σ, Γ′ , δ ′ , q0′ , X0 , ∅) donde Q′ = Q ∪ {q0′ , qv } (q0′ , qv ∈ / Q) Γ′ = Γ ∪ {X0 } X0 ∈ /Γ q0′ es el nuevo estado inicial. X0 es el nuevo s´ımbolo inicial de la pila. y δ ′ se define como: 1. δ ′ (q0′ , ǫ, X0 ) = {(q0 , Z0 X0 )} 2. δ(q, σ, γ) ⊆ δ ′ (q, σ, γ) ∀q ∈ Q ∀σ ∈ Σ ∪ {ǫ} ∀γ ∈ Γ. 3. (qv , ǫ) ∈ δ(qf , ǫ, γ) ∀qf ∈ F ∀γ ∈ Γ′ = Γ ∪ {X0 }. 4. (qv , ǫ) ∈ δ(qv , ǫ, γ) ∀γ ∈ Γ′ = Γ ∪ {X0 }.
... q
...
... 0
...
(a) Aut´omata original q’
0
(ε, γ , ε) 1 ... (ε , Z0 , ε ) (ε , X ,ε )
(ε , X , Z0 X ) 0 0 ...
0
q
...
...
q
0
...
(ε, γ , ε)
(ε, γ , ε)
... ( ε , Z0 , ε )
... ( ε , Z0 , ε )
1
(ε , X , ε ) 0
(b) Aut´omata transformado
v 1
(ε , X , ε ) 0
Sea P el aut´omata con pila de la siguiente figura:
q
(a, Z 0 , aZ0 ) 0
q
(b, Z0 , bZ0 )
(c, a, a) 1
q
(c, b, b)
($, Z 0 ,ε) 2
(a, a, ε) (b, b, ε)
(a, a, aa) (a, b, ab) (b, a, ba) (b, b, bb)
Se define como P ′ = (Q′ , Σ, Γ′ , δ ′ , q0′ , X0 , ∅) donde Q′ = Q ∪ {q0′ , qv } = {q0′ , qv , q0 , q1 , q2 , q3 } Σ = {a, b, c}, Γ′ = Γ ∪ {X0 } = {a, b, Z0 , X0 } q0′ es el nuevo estado inicial. X0 es el nuevo s´ımbolo inicial de la pila. y δ ′ se define como: Transici´on inicial (1) δ ′ (q0′ , ǫ, X0 ) = {(q0 , Z0 X0 )} Transiciones del aut´omata con pila P : (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12)
δ ′ (q0 , a, Z0) δ ′ (q0 , b, Z0 ) δ ′ (q1 , a, a) δ ′ (q1 , a, b) δ ′ (q1 , b, a) δ ′ (q1 , b, b) δ ′ (q1 , c, a) δ ′ (q1 , c, b) δ ′ (q2 , a, a) δ ′ (q2 , b, b) δ ′ (q2 , $, Z0)
= = = = = = = = = = =
{(q1 , aZ0 )} {(q1 , bZ0 )} {(q1 , aa)} {(q1 , ab)} {(q1 , ba)} {(q1 , bb)} {(q2 , a)} {(q2 , b)} {(q2 , ǫ)} {(q2 , ǫ)} {(q3 , a)}
Transiciones que pasan al estado que va a vaciar la pila de P ′: (13) (14) (15) (16)
δ ′ (q3 , ǫ, a) δ ′ (q3 , ǫ, b) δ ′ (q3 , ǫ, Z0 ) δ ′ (q3 , ǫ, X0 )
= = = =
{(qv , ǫ)} {(qv , ǫ)} {(qv , ǫ)} {(qv , ǫ)}
q
3
Transiciones del estado que vac´ıa la pila de P ′ : (13) (14) (15) (16)
δ ′ (qv , ǫ, a) δ ′ (qv , ǫ, b) δ ′ (qv , ǫ, Z0 ) δ ′ (qv , ǫ, X0 )
= = = =
{(qv , ǫ)} {(qv , ǫ)} {(qv , ǫ)} {(qv , ǫ)}
q’ 0
( ε, X0 , Z X0 ) 0
q
(a, Z 0 , aZ0 ) 0
(b, Z0 , bZ0 )
q
(c, a, a) 1
(c, b, b)
(a, a, aa) (a, b, ab) (b, a, ba) (b, b, bb)
q
($, Z 0 ,ε) 2
(a, a, ε) (b, b, ε)
q
3
(ε , Z0 , ε) (ε , X0 ,ε )
(ε , a, ε ) ( ε, b, ε )
q
(ε , a, ε ) ( ε, b, ε )
v
(ε , Z0 , ε ) (ε , X , ε ) 0
El an´alisis de la cadena abcba$ utilizando el aut´omata P ′ es: (q0′ , ǫabcba$, X0 ) ⊢1 ⊢2 ⊢6 ⊢9 ⊢11 ⊢10 ⊢12 ⊢16
(q0 , abcba$, Z0 X0 ) (q1 , bcba$, aZ0 X0 ) (q1 , cba$, baZ0 X0 ) (q2 , ba$, baZ0 X0 ) (q2 , a$, aZ0X0 ) (q2 , $, Z0X0 ) (q3 , ǫ, X0 ) (qv , ǫ, ǫ)
Como la pila est´a vac´ıa, la palabra abcba$ ∈ V (P ′).
Transformaci´ on de una aut´ omata con pila que utiliza el criterio de la pila vac´ıa en otro que utiliza el criterio del estado final. Dado P = (Q, Σ, Γ, δ, q0 , Z0 , ∅) que reconoce por el criterio de la pila vac´ıa, se puede construir un aut´omata con pila P ′ equivalente que reconoce por el criterio del estado final. Se define P ′ = (Q′ , Σ, Γ′ , δ ′ , q0′ , X0 , F ) donde Q′ = Q ∪ {q0′ , qf } (q0′ , qf ∈ / Q), Γ′ = Γ ∪ {X0 } X0 ∈ / Γ, q0′ es el nuevo estado inicial, X0 es el nuevo s´ımbolo inicial de la pila, F = {qf } y δ ′ se define como: 1. δ ′ (q0′ , ǫ, X0 ) = {(q0 , Z0 X0 )} 2. δ ′ (q, σ, γ) = δ(q, σ, γ) ∀q ∈ Q ∀σ ∈ Σ ∪ {ǫ} ∀γ ∈ Γ. 3. (qf , ǫ) ∈ δ ′ (q, ǫ, X0 ) ∀q∈ Q.
...
q
...
... 0
...
(a) Aut´omata original q’
0
(ε , X , Z X ) 0
0
0
...
(ε , X ε, ) 0
q
...
...
q
0
...
(ε , X ε, ) 0
(ε , X ε, ) 0
(ε , X ε, ) 0
(b) Aut´omata transformado
f
Sea P el aut´omata con pila de la siguiente figura:
q
(0, 0, ε ) (1, 1, ε ) 0
q
(ε , Z0 ,ε )
(0, 0,ε ) (1, 1, ε ) (ε , Z ,ε )
(0, Z , 0Z ) 0
1
0
(1, Z0 , 1Z0 ) (0, 0, 00) (0, 1, 01) (1, 0, 10) (1, 1, 11)
0
Se define como P ′ = (Q′ , Σ, Γ′ , δ ′ , q0′ , X0 , F ) donde Q′ = Q ∪ {q0′ , qf } = {q0′ , qf , q0 , q1 }, Σ = {0, 1}, Γ′ = Γ ∪ {X0 } = {0, 1, Z0, X0 }, q0′ es el nuevo estado inicial, X0 es el nuevo s´ımbolo inicial de la pila, F = {qf } es el conjunto de estado finales y δ ′ se define como: Transici´on inicial (1) δ ′ (q0′ , ǫ, X0 ) = {(q0 , Z0X0 )} Transiciones del aut´omata con pila P : (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)
δ(q0 , 0, Z0) δ(q0 , 1, Z0) δ(q0 , 0, 0) δ(q0 , 0, 1) δ(q0 , 1, 0) δ(q0 , 1, 1) δ(q1 , 0, 0) δ(q1 , 1, 1) δ(q0 , ǫ, Z0 ) δ(q1 , ǫ, Z0 )
= = = = = = = = = =
{(q0 , 0Z0)} {(q1 , 1Z0)} {(q0 , 00), (q1, ǫ)} {(q0 , 01)} {(q0 , 10)} {(q0 , 11), (q1, ǫ)} {(q1 , ǫ)} {(q1 , ǫ)} {(q1 , ǫ)} {(q1 , ǫ)}
Transiciones que pasan al estado final de P ′: (12) δ ′ (q0 , ǫ, X0 ) = {(qf , ǫ)} (13) δ ′ (q1 , ǫ, X0 ) = {(qf , ǫ)}
q’
(ε , X , Z X0 ) 0
0
q
0
(0, 0, ε ) (1, 1, ε ) 0
(ε , Z0 ,ε )
(0, Z 0 , 0Z ) 0
(1, Z0 , 1Z0 ) (0, 0, 00) (0, 1, 01) (1, 0, 10) (1, 1, 11)
(ε , X ,ε ) 0
(ε , X ,ε ) q
0
1
q
f
(0, 0,ε ) (1, 1, ε ) (ε , Z ,ε ) 0
El an´alisis de la cadena 0110$ utilizando el aut´omata P ′ es: (q0′ , 0110, Z0)
⊢1 ⊢2 ⊢6 ⊢7b ⊢8 ⊢11 ⊢13
(q0 , 0110, Z0X0 ) (q0 , 110, 0Z0X0 ) (o ⊢10 (q0 , 0110, X0)) (q0 , 10, 10Z0X0 ) (q1 , 0, 0Z0X0 ) (o ⊢7a (q1 , 0, 110Z0X0 )) (q1 , ǫ, Z0 X0 ) (q1 , ǫ, X0 ) (q3 , ǫ, ǫ)
Como qf ∈ F , la palabra 0110$ ∈ F (P ′).
Dado un aut´omata a pila P que utilice el criterio de la pila vac´ıa, se puede construir una gram´atica de contexto libre G equivalente, es decir, que verifique: V (P ) = L(G) Si P = (Q, Σ, Γ, δ, q0 , Z0, ∅) entonces se define la gram´atica de contexto libre G = (VN , VT , P, S) donde: VN = {[q, γ, q ′]|q, q ′ ∈ Q, γ ∈ Γ} ∪ {S}, donde S ∈ / Γ, VT = Σ, y el conjunto de reglas de producci´on se define mediante la aplicaci´on de las siguientes transformaciones: 1. Reglas de producci´on iniciales: ∀q ∈ Q (S −→ [q0 , Z0 , q] ∈ P )
(3)
2. Reglas de producci´on obtenidas a partir de transiciones que desapilan el s´ımbolo situado en la cima de la pila: ∀q, q ′ ∈ Q ∀σ ∈ Σ ∪ {ǫ} ∀γ ∈ Γ Si (q ′ , ǫ) ∈ δ(q, σ, γ) entonces [q, γ, q ′ ] −→ σ ∈ P
(4)
3. Reglas de producci´on obtenidas a partir de transiciones que insertan s´ımbolos en la pila: ∀q, q ′ , qi1 , qi2 , . . . , qik ∈ Q ∀σ ∈ Σ ∪ {ǫ} ∀γ, γj1 , γj2 , . . . , γjk ∈ Γ Si (q ′ , γj1 γj2 . . . γjk ) ∈ δ(q, σ, γ) entonces [q, γ, qik ] −→ σ[q ′ , γj1 , qi1 ][qi1 , γj2 , qi2 ] . . . [qik−1 , γjk , qik ] ∈ P (5) Se ha de tener en cuenta que se generar´a una regla de producci´on diferente para cada la elecci´on de los estados qi1 , qi2 , . . . , qik . Dicha elecci´on puede considerar que todos los estados son iguales, diferentes o cualquier otra combinaci´on posible.
Sea el aut´omata con pila P = (Q, Σ, Γ, δ, q0 , Z0 , ∅) donde Σ = {0, 1, $}, Γ = {Z0 , 0} y la funci´on de transici´on es: (1) (2) (3) (4) (5)
δ(q0 , 0, Z0) δ(q1 , 0, 0) δ(q1 , 1, 0) δ(q2 , 1, 0) δ(q2 , $, Z0)
q
= = = = =
(0, Z0 , 0Z0 ) 0
{(q1 , 0Z0 )} {(q1 , 00)} {(q2 , ǫ)} {(q2 , ǫ)} {(q2 , ǫ)}
Empezar Apilar Cambiar Desapilar T erminar
(1, 0, ε) q
q
1
0, 0, 00)
2
(1, 0, ε) ($, Z , ε) 0
Este aut´omata reconoce el lenguaje V (P ) = {0n 1n $|n ≥ 1} . Por ejemplo, el an´alisis de la cadena 0011$ es el siguiente: (q0 , 0011$, Z0) ⊢1 ⊢2 ⊢3 ⊢4 ⊢5
(q1 , 011$, 0Z0) (q1 , 11$, 00Z0) (q2 , 1$, 0Z0) (q2 , $, Z0) (q2 , ǫ, ǫ)
La gram´atica de contexto libre equivalente a P es G = (VN , VT , P, S) donde VN = { [q0 , Z0 , q0 ], [q0 , Z0 , q1 ], [q0 , Z0 , q2 ] [q0 , 0, q0 ], [q0 , 0, q1 ], [q0 , 0, q2 ] [q1 , Z0 , q0 ], [q1 , Z0 , q1 ], [q1 , Z0 , q2 ] [q1 , 0, q0 ], [q1 , 0, q1 ], [q1 , 0, q2 ] [q2 , Z0 , q0 ], [q2 , Z0 , q1 ], [q2 , Z0 , q2 ] [q2 , 0, q0 ], [q2 , 0, q1 ], [q2 , 0, q2 ] }
VT = Σ = {0, 1, $} y el conjunto de reglas de producci´on es: Reglas iniciales S −→[q0 , Z0 , q0 ] S −→[q0 , Z0 , q1 ] S −→[q0 , Z0 , q2 ] Reglas obtenidas a partir de transiciones que desapilan un s´ımbolo • Regla generada por la transici´on n´ umero 3: [q1 , 0, q2 ] −→ 1 • Regla generada por la transici´on n´ umero 4: [q2 , 0, q2 ] −→ 1 • Regla generada por la transici´on n´ umero 5: [q2 , Z0 , q2 ] −→ $ Reglas obtenidas a partir de transiciones que apilan s´ımbolos • Reglas generadas por la transici´on n´ umero 1: [q0 , Z0 , q0 ] −→0[q1 , 0, q0 ][q0 , Z0 , q0 ] [q0 , Z0 , q0 ] −→0[q1 , 0, q1 ][q1 , Z0 , q0 ] [q0 , Z0 , q0 ] −→0[q1 , 0, q2 ][q2 , Z0 , q0 ] [q0 , Z0 , q1 ] −→0[q1 , 0, q0 ][q0 , Z0 , q1 ] [q0 , Z0 , q1 ] −→0[q1 , 0, q1 ][q1 , Z0 , q1 ] [q0 , Z0 , q1 ] −→0[q1 , 0, q2 ][q2 , Z0 , q1 ] [q0 , Z0 , q2 ] −→0[q1 , 0, q0 ][q0 , Z0 , q2 ] [q0 , Z0 , q2 ] −→0[q1 , 0, q1 ][q1 , Z0 , q2 ] [q0 , Z0 , q2 ] −→0[q1 , 0, q2 ][q2 , Z0 , q2 ] • Reglas generadas por la transici´on n´ umero 2: [q0 , Z0 , q0 ] −→0[q1 , 0, q0 ][q0 , 0, q0 ] [q0 , Z0 , q0 ] −→0[q1 , 0, q1 ][q1 , 0, q0 ] [q0 , Z0 , q0 ] −→0[q1 , 0, q2 ][q2 , 0, q0 ] [q0 , Z0 , q1 ] −→0[q1 , 0, q0 ][q0 , 0, q1 ] [q0 , Z0 , q1 ] −→0[q1 , 0, q1 ][q1 , 0, q1 ] [q0 , Z0 , q1 ] −→0[q1 , 0, q2 ][q2 , 0, q1 ] [q0 , Z0 , q2 ] −→0[q1 , 0, q0 ][q0 , 0, q2 ] [q0 , Z0 , q2 ] −→0[q1 , 0, q1 ][q1 , 0, q2 ] [q0 , Z0 , q2 ] −→0[q1 , 0, q2 ][q2 , 0, q2 ]