Autómatas de Pila
Programación II
Margarita Álvarez
Autómatas de Pila Un autómata de pila consiste de: 1) Una unidad de control, que es un autómata finito. 2) Una memoria auxiliar que es una cinta semi-infinita con una clase particular de acceso restringido. La memoria de los autómatas de pila los hace más poderosos que los autómatas finitos. El acceso restringido a la memoria auxiliar es del tipo LIFO (last input first output). Tal memoria se denomina almacén pushdown o pila. Cinta de entrada
a b a b b a Cabeza lectora
q0
Control q1
qn
q2
qi q4
q3
Pila
Autómatas de Pila Un autómata de pila (pushdown automata) es:
A = (Q, ,, ,q0 ,z0 ,F) donde:
Q es un conjunto no vacío de estados. es el alfabeto de entrada, no vacío. es el alfabeto de la pila, no vacío. q0 Q es el estado inicial. F Q es el conjunto de estados finales. es la función de transición directa. Es una proyección: Q x ( ) x en subconjuntos finitos de Q x *. z0 : símbolo inicial de la pila.
Una configuración de un autómata de pila es una tripla c = (q , a , z) con q Q, a * , z *; q es el estado actual, a es el elemento a considerar de la hilera de entrada y z es el contenido de la pila.
Autómatas de Pila Entrada no procesada
a
Entrada Unidad de control en estado q
q
z
Pila
Funcionamiento o movimientos atómicos: Existen dos clases : 1) (q,a,z) = (p,w) donde: q : estado actual. a : símbolo de la hilera de entrada. z : símbolo del tope de pila. p : próximo estado. w : símbolo que se deja en el tope de pila. Al realizar el movimiento atómico la unidad de control pasa al estado p, el símbolo de entrada a se procesa y el símbolo z del tope de pila se reescribe como la hilera w *. • Si w = se borra, la pila pierde el primer símbolo de arriba. • Si |w| = 1, z se reemplaza por otro símbolo, posiblemente el mismo. • Si |w| > 1 se añaden símbolos a la pila.
Autómatas de Pila Entrada no procesada
a
Entrada Unidad de control en estado q
q
z
Pila
Funcionamiento o movimientos atómicos: Existen dos clases :
2) (q,,z) = (p,w) Al realizar este movimiento no se procesa ningún símbolo de entrada (la cabeza de entrada no se mueve). El autómata de pila puede cambiar de estado y modificar el contenido de la pila.
Convenciones para los diagramas de transición a
,
Símbolo que se toma de la hilera de entrada
b
a
/
Símbolo de tope de pila
b
Símbolo que se carga en el tope de pila
Símbolo anterior al que se carga
El símbolo a la derecha de la barra, como único elemento: a, b / significa que se borra de la pila el elemento que se encuentra como tope de pila. El símbolo a la izquierda de la barra significa fin de la hilera de entrada. L(G) = { an bn / n ≥ 1} a,a/aa
q0
a,z0/az0
q1
A = ({q0 ,q1 ,q2 ,q3}, {a,b}, {z0 ,a},,q0 ,z0 ,{q3 }) b,a/
b,a/
q2
,z0/z0
q3
(q0 ,a,z0 ) = (q1 ,a z0 ) (q1 ,a,a) = (q1 ,a a) (q1 ,b,a) = (q2 ,) (q2 ,b,a) = (q2 ,) (q2 ,,z0 ) = (q3 ,z0)
Autómatas de pila determinísticos y no determinísticos Los autómatas de pila son no determinísticos, si para algún: (q,a,z) Q x ( ) x , |(q,a,z)| > 1 Un autómata de pila es determinístico si |(q,a,z)| ≤ 1. Ejemplo de Autómata de Pila Determinístico L = {xcx-1 / x {a,b}*} un conjunto de palíndromas con marcador central c. A = ({q0 , q1 , q2}, {a,b,c}, {a,b,z0 }, , q0 , z0 , {q2}) (q0 ,a,z0 ) = (q0 ,a z0 ) (q0 ,b,z0 ) = (q0 ,b z0 ) (q0 ,a,a) = (q0 ,a a) (q0 ,b,b) = (q0 ,b b) (q0 ,a,b) = (q0 ,a b)
(q0 ,b,a) = (q0 ,b a) (q0 ,c,z0 ) = (q1 ,z0 ) (q0 ,c,a) = (q1 ,a) (q0 ,c,b) = (q1 ,b) (q1 ,a,a) = (q1 ,) (q1 ,b,b) = (q1 , ) (q1 , ,z0 ) = (q2 ,z0 )
a,z0/az0 b,z0/bz0 a,a/aa b,b/bb a,b/ab b,a/ba
q0
c,z0/z0 c,a/a c,b/b
a,a/
b,b/
q1
,z0/z0
q2
Autómatas de pila determinísticos y no determinísticos Ejemplo de Autómata de Pila No Determinístico L = {xx-1 / x {a,b}*} un conjunto de palíndromas sin marcador central. A = ({q0 , q1 , q2}, {a,b}, {a,b,z0 }, , q0 , z0 , {q2})
(q0 ,a,z0 ) = (q0 ,a z0 ) (q0 ,b,z0 ) = (q0 ,b z0 ) (q0 ,a,a) = (q0 ,a a) (q0 ,b,b) = (q0 ,b b) (q0 ,a,b) = (q0 ,a b)
(q0 ,b,a) = (q0 ,b a) (q0 ,a,a ) = (q1 , ) (q0 ,b,b) = (q1 , ) (q0 , ,z0 ) = (q2 ,z0 ) (q1 ,a,a) = (q1 ,) (q1 ,b,b) = (q1 , ) (q1 , ,z0 ) = (q2 ,z0 )
a,z0/az0 b,z0/bz0 a,a/aa b,b/bb a,b/ab b,a/ba
q0
a,a/ b,b/
a,a/
b,b/
q1
,z0/z0
q2
,z0/z0
Es no determinístico debido a: (q0 ,a,a) = {(q0 ,a a), (q1 ,)} (q0 ,b,b) = {(q0 ,b b), (q1 , )} No siempre es posible, dado un autómata de pila no determinístico, encontrar un autómata de pila determinístico que acepte el mismo lenguaje.
Conclusiones
El AP tiene más poder que el finito.
La memoria (dada por la pila) es de acceso limitado, para acceder a un cierto dato es necesario borrar los anteriores. Esto impide, por ejemplo, reconocer el lenguaje: L(G) = {anbncn / n ≥1} Se ve entonces la necesidad de disponer otro modelo computacional, que se presenta como otro tipo de autómata, cuya memoria no tenga esas limitaciones. Este modelo es la máquina de Turing. Cada tipo de autómata definido, incluye al anterior como caso particular.
