04-AutomatasPila-2019(color)

Vista previa del material en texto

Teoría de la Computabilidad –Prof. Carlos Iván Chesñevar
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Teoría de la
Computabilidad– Transparencias de Clase”.  Dr. Chesñevar, Mg. Cobo, Dr. Martínez. Univ. Nac. Del Sur
1
Teoría de la 
Computabilidad
Departamento de Cs. e Ing. de la Computación
Universidad Nacional del Sur
Bahía Blanca, Argentina
Módulo 4:
Autómatas a Pila
2
Autómatas a Pila (AP)
Hemos visto que los Lenguajes Regulares (Tipo 3) son 
generables por Gramáticas Regulares, y reconocibles 
por Autómatas Finitos.
Nos concentraremos ahora en los Lenguajes Libres de 
Contexto (o tipo 2). 
Veremos un dispositivo que reconoce lenguajes LC 
llamado Autómata a Pila (en inglés Pushdown 
automaton)
3
Autómatas a Pila (AP) - Esquema general
a b c d e f ......
Control de 
Estados
Pila de 
Símbolos
El AF posee 
ahora una 
estructura de 
datos auxiliar...
..es capaz de apilar o 
desapilar símbolos en 
una pila
La pila le da mayor poder al formalismo, pues el autómata 
ahora puede “recordar” lo leído en la cinta...
4
Autómatas a Pila (AP) - Esquema general
a b c d e f ......
Control de 
Estados
a
Pila de 
Símbolos
Los cambios de estado son 
definidos ahora por el 
símbolo leído en la cinta, y 
por el tope de la pila.
Además de cambiar de estado, en la transición podremos 
agregar o quitar elementos de la pila...
5
Autómata a Pila (Pushdown automaton)
Def.: Un autómata a pila determinista (APD) P es una
6-tupla (S, , , , s0 , F), donde:
• S es un conjunto finito de estados, S Ø.
•  es un alfabeto de entrada.
•  es el alfabeto de la pila.
•  : S x {  {}} x * S x *
• s0 S es el estado inicial del APD.
• F  S es el conjunto de estados finales o
aceptadores.
Observación: notar que hay alfabeto de entrada  y 
alfabeto de pila . Eventualmente pueden ser iguales.
•  es el alfabeto de la pila.
•  : S x {  {}} x * S x *
6
Notación. Conceptos Importantes
(s0, b, a) = (s1, ba)
estado actual
símbolo leído
símbolo en tope de pila
nuevo estado
acción sobre la pila
a b a a ......
S0 a
a b a a ......
S1 a
b
Teoría de la Computabilidad –Prof. Carlos Iván Chesñevar
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Teoría de la
Computabilidad– Transparencias de Clase”.  Dr. Chesñevar, Mg. Cobo, Dr. Martínez. Univ. Nac. Del Sur
7
Configuración
Def.: Sea P=(S, , , , s0 , F) un APD. Una
configuración es una terna (s,w,) S x *x *
Representa el estado global del APD P.
s = estado en curso
w = parte aún no leída de la cadena
 = contenido de la pila (símbolo más a la izq en  es 
el tope de pila; inicialmente  = )
Si w = , entenderemos que la cadena fue leída (o sólo 
restan acciones que no consumen caracteres)
(s0, w, )
Estado inicial s0: La pila está 
vacía, y toda la cadena w está por 
ser procesada.
8
Transición
Def.: Una transición de P es representada con una
relación binaria “|-” entre configuraciones: (s,aw, z) |-
(s’,w,) si (s,a,z)= (s’, ), donde s,s’S; a{},
w* ; z, ,  *.
Una transición indica la evolución del autómata. 
Si a   esto determina que si la situación de origen 
es estado s, símbolo actual a, y símbolo en tope de 
pila = z, entonces se pasa a estado s’, se desplaza la 
cabeza lecto-escritora un lugar a derecha, y el tope de 
pila se reemplaza con . 
Si  = , entonces se dice que P está desapilando.
9
Transición. -Movimientos
Una transición indica la evolución del autómata.
Si a= , esto se llama un -movimiento
Si a=, el símbolo actual no es tomado en
consideración, y la cabeza no se mueve. Pero ...el
estado puede ser cambiado, y la pila actualizada! Un
-movimiento puede ocurrir aún si toda la cadena ya
ha sido leída.
Def.: Una transición de P es representada con una
relación binaria “|-” entre configuraciones: (s,aw, z) |-
(s’,w,) si (s,a,z)= (s’, ), donde s,s’S; a{},
w* ; z, ,  *.
10
Reconocimiento de cadenas
Def.: Se dice que una cadena w es aceptada o
reconocida por un AP P=(S, , , , s0 , F) si (s0,w, )
|–* (sf, , ) para algún sf  F.
Definimos el lenguaje aceptado por P como
L(P)={w|w es aceptada por P}.
Por convención, un AP acepta cadenas cuando
1) termina de procesar completamente la cadena de
entrada en un estado aceptador, y
2) su pila está vacía.
El AP se detendrá cuando llega a una configuración
para la cual la función  no ha sido definida, o se ha
consumido la cadena de entrada.
11
Función de Transición: ejemplos
(s0, b, a) = (s1, ba)
Si estado actual = S0
y símbolo leído = b
y tope de pila = a
entonces nuevo estado es S1
apilar b sobre la a
(s0, b, ) = (s1, b)
Si estado actual = S0
y símbolo leído = b
y la pila está vacía
entonces nuevo estado es S1
apilar b
12
Función de Transición: ejemplos
(s3, b, a) = (s4, )
Si estado actual = S3
y símbolo leído = b
y tope de pila = a
entonces nuevo estado es S4
desapilar el tope de la pila
a b a a ......
S3 a
a b a a ......
S4
Teoría de la Computabilidad –Prof. Carlos Iván Chesñevar
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Teoría de la
Computabilidad– Transparencias de Clase”.  Dr. Chesñevar, Mg. Cobo, Dr. Martínez. Univ. Nac. Del Sur
13
Función de Transición: ejemplos
(s3, , b) = (s3, )
Si estado actual = S3
sin consumir nada de la cinta
y tope de pila = b
entonces nuevo estado es S3
desapilar el tope de la pila
a b a a ......
S3 b
a b a a ......
S3
14
Función de Transición: ejemplos
(s3, c, ba) = (s3, ab)
Si estado actual = S3
y símbolo leído = c
y tope de pila = ba
entonces nuevo estado es S3
Reemplazar el tope ba por ab
a c a a ......
S3
a
b
a c a a ......
S3
b
a
15
Función de Transición: ejemplos
(s3, , S) = (s4, [ ])
Si estado actual = S3
sin consumir nada de la cinta
y tope de pila = S
entonces nuevo estado es S4
desapilar S y apilar [ ]
a b a a ......
S3 S
a b a a ......
S4 ]
[
16
Función de Transición: ejemplos
(s3, , ) = (s4, )
Si estado actual = S3
sin consumir nada de la cinta
y la pila está vacía,
entonces nuevo estado es S4
mantenemos la pila vacía
Ocasionalmente  será una acción que sirve para llegar a
un estado final o aceptador.
Ejemplo: supongamos que s4 es un estado final.
Entonces la configuración a la que se arriba después de
la transición anterior es de aceptación, esto es (s4, , ).
17
Ejemplo 1 
Desarrollar un AP para L = {0n1n|n0}.
Sea P=(S, , , , s0 , F) un AP, donde
S= {s0,s1,s2,s3},  = {0,1},  = {0}, F= {s3}
Idea: P copia los ‘0’ de la 
cadena de entrada en la 
pila, y luego desapila un 
‘0’ por cada ‘1’ leído. Las 
principales operaciones 
del AP pueden definirse 
como:
(s0, ,  ) = (s3, )
(s0, 0,  ) = (s1, 0)
(s1, 0, 0 ) = (s1, 00)
(s1, 1, 0 ) = (s2,  )
(s2, 1, 0 ) = (s2,  )
(s2, , ) = (s3,  )
18
Ejemplo 1 (cont.)
De s0 con cadena  y pila 
vacía, se pasa a s3
Desde s0 al leer 0 y tener pila 
vacía, paso a s1 y apilo 0
Desde s1 al leer 0 y c/ tope de 
pila un 0, sigo en s1 y apilo 0
Desde s1 al leer 1 y con tope de 
pila un 0, paso a s2 y desapilo
En s2 al leer 1 y tener en tope 
pila un 0, desapilo
En s2 al leer cadena. vacía y tener pila 
vacía, paso a s3 y acepto
(s0, ,  ) = (s3, )
(s1, 0, 0 ) = (s1, 00)
(s0, 0,  ) = (s1, 0)
(s1, 1, 0 ) = (s2,  )
(s2, 1, 0 ) = (s2,  )
(s2, , ) = (s3,  )
Teoría de la Computabilidad –Prof. Carlos Iván Chesñevar
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Teoría de la
Computabilidad– Transparencias de Clase”.  Dr. Chesñevar, Mg. Cobo, Dr. Martínez. Univ. Nac. Del Sur
19
Ejemplo 1 (cont.)
(s0, ,  ) = (s3, )
(s0, 0,  ) = (s1, 0)
 (s1, 0, 0 ) = (s1, 00)
 (s1, 1, 0 ) = (s2,  )
 (s2, 1, 0 ) = (s2,  )
 (s2, , ) = (s3,  )
Con la cadena de entrada 0011en P, resultan las sgtes.
transiciones de configuraciones
(s0, 0011,  ) |– (s1, 011, 0) |– (s1, 11, 00) |– (s2, 1, 0) |–
|– (s2,  , ) |– (s3,  , )  0011 es aceptada
Atención: En otros libros de texto
(y en los softwares como
DeuxExMachina) se utilizan
convenciones diferentes para
representar Autómatas a Pila...
20
Representacion Gráfica de un AP
En la práctica utilizaremos una representación de
AP por medio de grafos, de forma similar a los
autómatas finitos.
Cada estado será representado por un nodo del
grafo. La función  se representará por medio de
arcos etiquetados con: el símbolo que se está
procesando, mas el estado de la pila antes y
después de realizar tal procesamiento.
En general (si,α,β)=(sj,γ) donde si, sjS , α{}, y
β,γ* se representa en el grafo de la sig. forma:
si sj
α, β / γ
21
Representación Gráfica AP Ejemplo 1 
AP para L = {0n1n|n0}.
Sea P=(S, , , , s0 , F) un AP, donde
S= {s0,s1,s2,s3},  = {0,1},  = {0}, F= {s3}
(s0, ,  ) = (s3, )
(s0, 0,  ) = (s1, 0)
(s1, 0, 0 ) = (s1, 00)
(s1, 1, 0 ) = (s2,  )
(s2, 1, 0 ) = (s2,  )
(s2, , ) = (s3,  )
s0 s3
, /
s1
0, 0/00
s2
1, 0/
1, 0/
Estado Final 
(doble circulo)
22
Ejemplo 2 
Desarrollar un AP para
L = {w{a,b}*, donde w tiene igual nro. de a y b}.
Idea:
Apilar la letra si coincide con la del tope, y
desapilarla en caso contrario. Si en la pila quedan
a’s, indica que hay mayor nro. de a’s que de b’s.
23
Ejemplo 2 (cont.)
P=(S, , , , s0 , F)
S= {s0,s1},
= {a,b},
F= {s1}
(s0, a,  ) = (s0, a)
(s0, a, a ) = (s0, aa)
(s0, a, b ) = (s0, )
(s0, b, ) = (s0, b )
(s0, b, b ) = (s0, bb)
(s0, b, a) = (s0,  )
(s0, , ) = (s1,  )
Desarrollar un AP para
L = {w{a,b}*, donde w tiene igual nro. de a y b}.
24
Autómata a Pila No Determinista (APND)
Def.: Un autómata a pila no determinista (APND) P es
una 6-tupla P= (S, , , , s0 , F), donde:
• S es un conjunto finito de estados, S Ø.
•  es un alfabeto de entrada.
•  es el alfabeto de la pila.
•  : S x {  {}} x * Partes(S x *)
• s0 S es el estado inicial del APND.
• F  S es el conjunto de estados finales o
aceptadores.
•  : S x {  {}} x * Partes(S x *)
Teoría de la Computabilidad –Prof. Carlos Iván Chesñevar
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Teoría de la
Computabilidad– Transparencias de Clase”.  Dr. Chesñevar, Mg. Cobo, Dr. Martínez. Univ. Nac. Del Sur
25
Ejemplo APND
Sea
P=(S, , , , s0 , F)
S= {s0,s1,s2},
= {a,b},
 = {a,b},
F= {s2}
(s0, a, ) = { (s0, a) }
(s0, b, ) = { (s0, b) }
(s0, a,a) = { (s0, aa), (s1, ) }
(s0, a, b ) = { (s0, ab) }
(s0, b, a ) = { (s0, ba ) }
(s0, b, b) = { (s0, bb), (s1,  )}
(s1, a, a ) = { (s1, ) }
(s1, b, b ) = { (s1,  ) }
(s1, , ) = { (s2,  ) }
Diseñar un APND P para 
L={wwr|w {a,b}+}
26
Dos secuencias posibles
Ejemplo: consideremos la cadena abba
(s0, abba,  ) |–
(8) (s0, bba, a) |–
(12) (s0, ba, ba)
|–(13,opción1) (s0, a, bba) |–
(11) (s0, , abba)
En este caso la cadena no es reconocida
(s0, abba,  ) |–
(8) (s0, bba, a) |–
(12) (s0, ba, ba)
|–(13,opción2) (s1, a, a) |–
(14) (s1, , ) |–
(16) (s2, , )
En este caso la cadena es reconocida
27
L(APND)
Reflexiones sobre APD vs. APND
L={wwr|w {a,b}+} no puede ser reconocido por un AP
determinista, pero sí por un AP no determinista.
Intuitivamente, vemos que un APND es más “potente”
que un AP. Formalmente:
Teorema: Los APND tienen mayor poder de
reconocimiento de lenguajes que los APD.
L(APD)
28
AP y Gramáticas Libres de Contexto
¿Que relación existe entre los autómatas a pila y las 
gramáticas libres de contexto?
Esta equivalencia es sumamente útil al momento de
implementar analizadores sintácticos para lenguajes de
programación.
Antes de probar formalmente esta equivalencia, daremos
algunas definiciones auxiliares...
Respuesta
Los APND reconocen exactamente la clase de 
lenguajes generados por las GLC.
29
Definiciones auxiliares
Sea G = (Vn,Vt,S,P) una GLC. Ent. wL(G) sssi
w  Vt* y existe una derivación
S 12 3...  w 
con cadenas i (Vn  Vt)
+.
Diremos que una derivación es una derivación a
izquierda si el símbolo no terminal reemplazado en
cada paso es el ubicado más a la izquierda.
Ejemplo: sea G = (Vn,Vt,S,P), Vn = {S}, Vt = { ], [ } y P =
{S [ ], S SS, S [S] }. Según la def. anterior,
S SS [ ]S [ ][ ] es una derivación a izq.
SSSS[ ][ ][ ] no lo es.
30
Teorema de Equivalencia entre APND y LLC
Teorema: La clase de lenguajes aceptados por
APND es exactamente la clase de LLC.
La demostración será por doble implicación:
a) Si un lenguaje es LC, entonces es aceptado por un
APND [demostración a continuación]
b) Si un lenguaje es aceptado por un APND, entonces
es LC [sin demostración]
Teoría de la Computabilidad –Prof. Carlos Iván Chesñevar
El uso total o parcial de este material está permitido siempre que se haga mención explícita de su fuente: “Teoría de la
Computabilidad– Transparencias de Clase”.  Dr. Chesñevar, Mg. Cobo, Dr. Martínez. Univ. Nac. Del Sur
31
Si L es LLC  L es aceptado por APND
Sea G = (Vn,Vt,S,P) una GLC. Construiremos un AP P tal
que L(G)=L(P).
El autómata P tendrá sólo dos estados: s0 y s1. Luego del
primer movimiento, P estará siempre en estado s1. P
simulará las derivaciones de la cadena de la gramática,
usando Vn  Vt como alfabeto de la pila.
Definiremos P = ({s0,s1}, Vt , Vn  Vt , , s0, {s1}), con:
(s0 , , ) = {(s1,S)} (apila S, símbolo inicial de G)
(s1 , , 1)  {(s1,2)} para cada regla 1 2 P.
(s1 , a, a) = {(s1, )} para cada aVt.
32
Si L es LLC  L es aceptado por APND
 o bien se reemplaza el no terminal A del tope de la
pila por la parte derecha de la producción que le
corresponde,
 o bien se desapila el símbolo del tope si coincide
con la entrada.
El Autómata comenzará apilando S, el símbolo inicial
de G, y pasa a estado s1. En cada paso que sigue:
Las transiciones hacen la “mímica” de una derivación 
a izquierda en caso que la cadena de entrada 
pertenezca al lenguaje.
Si L(G), basta agregar el estado inicial de P a su 
conjunto de estados finales.
33
Ejemplo LLCAPND
Sea la gramática G=(Vn,Vt,S,P), con Vn={S}, Vt={[,]}, P={ 
S[ ], SSS, S[S]}. 
Intentaremos usar el teorema para construir un APND
que reconozca este lenguaje.
Sea P= (K,,,,s0,F)
con
K={s0, s1},
={[,]},
={ S, [, ] } y
F={s1 }.
(s0, ,  ) = { (s1, S) }
(s1, , S ) = { (s1, [ ]) }
(s1, , S ) = {(s1, SS)}
(s1, , S ) = {(s1,[S] )}
(s1, [, [ ) = {(s1,  )}
(s1, ], ]) = {(s1,  )}
34
Ejemplo LLCAPND (cont.)
(s0, [ ] [ ],  )
|– (s1, [ ] [ ], S )
|– (s1, [ ] [ ], SS )
|– (s1, [ ] [ ], [ ]S )
|– (s1, ] [ ], ]S )
|– (s1, [ ], S )
|– (s1, [ ], [ ])
|– (s1, ], ])
|– (s1, , )
(s0, ,  ) = { (s1, S) }
(s1, , S ) = { (s1, [ ]) }
(s1, , S ) = {(s1, SS)}
(s1, , S ) = {(s1,[S] )}
(s1, [, [ ) = {(s1,  )}
(s1, ], ]) = {(s1,  )}
¿ Acepta la 
cadena [ ][ ] ?
cadena [ ][ ]