300CIG007

Computabilidad y Lenguajes Formales: Autómatas de Pila Pontificia Universidad Javeriana Cali Ingeniería de Sistemas y Computación Prof. Gloria Inés Alvarez V. Basado en [SIPSER, Chapter 2]

Autómatas de Pila (PushDown Autómata – PDA) 

Un PDA se compone de dos cintas (pueden ser de longitud infinita), la primera cinta contiene la entrada (cadena que va a ser reconocida), y la segunda una pila. Pila



Son equivalentes en poder de expresión a las Gramáticas Libres de Contexto

Entrada a

x y z

a

a

b

Control de Estados

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Autómatas de Pila (PDA) 

Formalmente un PDA es una 7-tupla (Q, ∑, Γ, δ, q0, z0, F), donde: 

 

Q es un conjunto finito de estados

∑ es el alfabeto de entrada (un conjunto finito) Γ es el alfabeto de la pila (un conjunto finito)



δ : Qx∑εxΓε → P(QxΓε) es la función de transición



q0 ∈ Q es el estado de inicio



z0 ∈ Γ es el símbolo de inicio



F ⊆ Q es el conjunto de estados de aceptación (un

conjunto finito) Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Autómatas de Pila (PDA) 

Un PDA funciona realizando dos tipos de movimientos: 

Movimientos que dependen del símbolo siguiente en la cadena de entrada: δ(q, a, z) = { (p1, γ1), (p2, γ2), … (pm, γm) } Donde q y pi, 1≤ i ≤ m, son estados, a ∈ ∑, z ∈ Γ, γi∈ Γ*, 1≤ i ≤ m, tales que cuando el PDA está en el estado q, con el símbolo de entrada a, y z en el tope de la pila, para algún i, el PDA entra al estado pi, reemplaza a z por la cadena γi, y avanza en la cadena de entrada.

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Autómatas de Pila (PDA) 

Un PDA funciona realizando dos tipos de movimientos: 

ε-movimientos: δ(q, ε, z) = { (p1, γ1), (p2, γ2), … (pm, γm) } Donde q y pi, 1≤ i ≤ m, son estados, z ∈ Γ, γi∈ Γ*, 1≤ i ≤ m, tales que cuando el PDA está en el estado q, independiente del símbolo en la cadena de entrada, con z en el tope de la pila, para algún i, el PDA puede entrar al estado pi, reemplaza a z por la cadena γi.

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Autómatas de Pila (PDA): Ejemplo 

M = (Q, ∑, Γ, δ, q0, $, F), donde:  Q = {q , q , q ,q } a,ε → a 0 1 2 3 b,ε → b  ∑ = { a, b, c }, Γ = { a, b, $ } ε,ε → $ q0 q1  δ = { (q , ε, ε) → (q , $), 0 1 (q1, a, ε) → (q1, a), c,ε → ε (q1, b, ε) → (q1, b), q2 a,a → ε (q1, c, ε) → (q2, ε), b,b → ε ε,$ → ε q3 (q2, a, a) → (q2, ε), (q2, b, b) → (q2, ε), (q2, ε, $) → (q3, ε) }  F = {q } Que lenguaje reconoce este PDA? 3

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

PDA Determinista 

Un PDA M = (Q, ∑, Γ, δ, q0, $, F), es determinista si: 





Para todo q ∈ Q y z ∈ Γ, siempre que δ (q, ε, z) no es vacío, entonces δ (q, a, z) es vacía para todo a ∈ ∑ No existe un q ∈ Q, z ∈ Γ, y a ∈ ∑ε , tal que δ (q, a, z) contiene mas de un elemento.

Los PDA Deterministas no son equivalentes a los PDA no deterministas, en cuanto al conjunto de lenguajes que aceptan. Ejemplo: que sucede con el lenguaje L = { wwR : w ∈ {a, b}* }?

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Equivalencia de PDA y CFG Teorema: Un Lenguaje es Libre de Contexto (CFL) si y solo si existe algún autómata de pila que lo reconoce Lema 1: Si un Lenguaje es Libre de Contexto (CFL) entonces existe algún autómata de pila que lo reconoce Lema 2: Si un autómata de pila reconoce un lenguaje, entonces el Lenguaje es Libre de Contexto (CFL)

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Equivalencia de PDA y CFG: Lema 1 Sea A un CFL, por definición A tiene una CFG G que lo genera, entonces es necesario convertir G en un PDA P capaz de reconocer A. P puede funcionar de la siguiente manera:  Adicione a la pila un símbolo que marque el inicio ($) y el símbolo inicial de G  Repita: 





Si en el tope de la pila esta un no terminal N, de manera aleatoria seleccione una de las reglas producción de N, N→Y1 Y2 …Yk, y sustituya en la pila N por los símbolos del lado derecho de la regla seleccionada, en orden inverso (pop N, push(Yk ), push(Yk-1 ), … push(Y2 ), push(Y1) Si en el tope de la pila hay un símbolo terminal a, lea el siguiente símbolo de la cadena de entrada y comparelo con a, si coinciden haga pop de a. Si no coinciden, rechace esta rama del no-determinismo. Si en el tope de la pila está el simbolo $, entre en el estado de aceptación.

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Equivalencia de PDA y CFG: Lema 1 Formalmente, P = (Q, ∑, Γ, δ, q0, $, F), se construye así: Q = { qstart, qloop, qaccept} δ(qstart, ε, ε) = (qloop, S$) , donde S es el símbolo inicial de la gramática

δ(qstart, ε, ε) = (qloop, S$) , donde S es el símbolo inicial de la gramática

δ(qloop, ε, N) = {(qloop, w) : N→w es una regla de producción de G } δ(qloop,a, a) = { (qloop, ε) } , donde a ∈ ∑ δ(qloop,, ε, ε) = { (qaccept, ε) } Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Equivalencia de PDA y CFG: Lema 1: Ejemplo Dada G = (N, Σ, P, S), N = { S }, Σ = { a, b }, P = { S → a S b, S → a b }

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Equivalencia de PDA y CFG: Lema 2 Si un autómata de pila reconoce un lenguaje, entonces el Lenguaje es Libre de Contexto (CFL) El automáta de pila debe cumplir las siguientes condiciones. 

Tiene un solo estado de aceptación qf, al cual llega si y solo si la pila esta vacía



Cada transición hace un push o un pop de la pila, pero no ambos.

Todo NPDA tiene un NPDA equivalente que cumple las dos condiciones. Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Equivalencia de PDA y CFG: Lema 2 Si se crea una gramática cuyos símbolos no terminales son de la forma Apq, donde p y q ∈ Q Sea P = (Q, ∑, Γ, δ, q0, $, {qaccept}), se construye la gramática G

de la siguiente manera:

El símbolo inicial es Aq0qaccept  Para todo p, q, r, s ∈ Q, t ∈ Γ, y a,b ∈ ∑ ε si δ(p,a,Ɛ) contiene (r,t), y δ(s,b,t) contiene (q, Ɛ), agregue la regla Apq → aArsb  Para todo p,q,r ∈ Q agregue la regla Apq → AprArq  Para todo p ∈ Q agregue la regla App → Ɛ 

Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Computación – 300CIG007 –

Prof. Ma. Constanza Pabón

Pumping Lema para CFL Teorema: Si A es un Lenguaje Libre de Contexto (CFL) entonces existe un numero p (pumping length) donde, si s es alguna cadena que pertenece a A de longitud mayor o igual a p, entonces s puede ser dividido en 5 partes s = uvxyz que satisfacen las siguientes condiciones:

 Para todo i >= 0, uvixyiz ∈A,  |vy| > 0  |vxy|