Automatas_de_pila_Completo

06/05/2013

Teoría de la
Computación

M. en I. Jorge Carlos Reyes Magaña



Pila
◦ Último en entrar primero en salir

Solamente se puede introducir
por el tope de la pila

1

06/05/2013





Recordemos que los Autómatas Finitos no
son lo suficientemente poderosos para
aceptar los Lenguajes libres de contexto.
Autómatas de pila
◦ Tienen la estructura de un AF: estados y
transiciones.
q0

q1Los elementos en las transiciones cambian



Transiciones en Autómatas de Pila.


Se registran los caracteres de entrada y los movimientos de la pila.
ω/α/β
q1

Ahora las transiciones tienen 3 partes:
1. ω = Entrada (elemento de la cadena a ser parseado)
2. α = Sale de la pila
3. β = Entra a la pila
Primero se ejecuta la operación de sacar de la pila y luego de meter

2

06/05/2013





Paradiseñar un AP se tiene que repartir lo
que se requiere ser “recordado” entre los
estados y la pila.

Distintos diseños para un mismo problema
pueden tomar decisiones diferentes en
cuanto a qué recuerda cada cual.



Ejemplo: Diseñar un AP que acepte
exactamente el lenguaje con palabras de la
forma anbn, para cualquier número natural.
◦ Ejemplo usando un contador

a//a
b/a/ 
q

6

3

06/05/2013cadena/ Saca/ Entra



Traza de ejecución para w = aabb
Estado
q
q
q
q
q

Por leer
aabb
abb
bb
b
ε

Pila
Vacía
a
aa
a
Vacía

a/  /a
b/a/ 
q

7



Problema!!!
◦ El AP también acepta palabras como abab
(corroborar con la traza de ejecución).
◦ El AP no tiene la forma deseada: anbn
◦ No se ha recordado cuando se terminan las a’s e
inician las b’s.



Solución
◦ Utilizar los estados paramemorizar las situaciones
de estar consumiendo a’s o estar consumiendo b’s.

8

4

06/05/2013



anbn

cadena/ Saca/ Entra

b/a/ 

a//a
b/ a/ 

q0


q1

Ejemplo:

aaabbb

aaabbb

aaabbb

aaabbb

aaabbb

La pila esta vacía
y se llega a un
estado aceptado
(q1), por lo tanto
la palabra se
acepta
aaabbb

a
a

a

a

a

a

a

a

a

q0

q0

q0

q1

q1

q1



Ejemplo: Proponer un AP para el lenguaje delos palíndromos con número par de símbolos
en {a,b}, esto es, palabras que se leen igual de
izquierda a derecha y viceversa, y por lo tanto
tienen la forma wwR donde wR es el reverso de
w (invertir el orden).
Ejemplos:



¿Cual sería la estrategia a seguir?



◦ abba, aa, bbbbbb
◦ aab, aabaa

(correctos)
(incorrectos)

10

5

06/05/2013

cadena/ Saca/ Entra



Estrategia:
◦ Almacenar en la pilala primera mitad de la
palabra y luego ir comparándola letra por
letra contra la segunda mitad.

a/  /a

b/  /b

s

//

b/b/ 

a/a/ 
f

11



Consideraciones:
◦ La presencia de una transición de s a f, en que ni se
consumen caracteres de la entrada, ni se manipula
la pila.
◦ ¿Se puede llegar a un estado final sin recorrer la
mitad de la palabra?
◦ ¿Cómo saber que ya llegamos exactamente ala
mitad de la palabra?

12

6

06/05/2013





En un AFN una palabra es aceptada cuando
existe un cálculo que permite aceptarla,
independientemente de que un cálculo en
particular se vaya por el camino erróneo.
Lo importante es que exista un cálculo que
acepte la palabra en cuestión.

13

cadena/ Saca/ Entra

a/  /a
s


b/b/ 

b/  /b
//

a/a/ 
f

Traza de ejecución para w = abbaEstado
s
s
s
f
f
F

Por leer

Pila

abba
bba
ba
ba
a

Pila vacía
a
ba
ba
a
 Pila vacía
14

7

06/05/2013





Se pueden aplicar métodos de combinación
modular de autómatas, como se realizaron
con los AF.
Dados dos AP M1 y M2 y que aceptan los
lenguajes L1 y L2 respectivamente, se puede
obtener un AP que acepte la unión L1 U L2
introduciendo un nuevo estado inicial s0 con
transiciones  /  /  a losdos antiguos
estados iniciales de M1 y M2.

15



Un AP es un séxtuplo (K, Σ, Γ, Δ, s,
F) donde:
◦
◦
◦
◦
◦
◦

K es un conjunto de estados
Σ es el alfabeto de entrada
Γ es el alfabeto de la pila
.   ( K x* x * ) x( K x * )
s Є K es el estado inicial
. F K

16

8

06/05/2013



Si se tiene una transición de la forma
((p,u,β),(q,γ)) Є Δ:
◦
◦
◦
◦




Estando en el estado p, consume u de...