Autómatas
de Pila
Los autómatas de
pila, en forma similar a como se usan los autómatas finitos, también
se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un
alfabeto A.
Los autómatas de
pila pueden aceptar lenguajes que no pueden aceptar los autómatas
finitos.
Un autómata de pila
cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse
en uno de entre un número finito de estados. Uno de estos estados
se designa como estado inicial, y además algunos estados se llaman
de aceptación o finales. A diferencia de los autómatas finitos,
los autómatas de pila cuentan con una memoria auxiliar llamada pila.
Los símbolos (llamados símbolos de pila) pueden ser insertados
o extraídos de la pila, de acuerdo con el manejo last-in-first-out
(LIFO).
Las transiciones entre los
estados que ejecutan los autómatas de pila dependen de los símbolos
de entrada y de los símbolos de la pila. El autómata acepta
una cadena x si la secuencia de transiciones, comenzando en estado inicial
y con pila vacía, conduce a un estado final, después de leer
toda la cadena x.
Autómata
de pila reconocedor determinístico
Autómata
de pila no determinístico
Como ya se ha estudiado los
autómatas finitos no determinísticos (AFND) reconocen los
mismos lenguajes que los autómatas finitos determinísticos
(AFD). Sin embargo no ocurre lo mismo con autómatas de pila no determinísticos
(APND) y autómatas de pila determinísticos (APD). Algunos
lenguajes sólo pueden ser reconocidos por un APND, pero no por un
APD.
Autómata
de pila traductor
Función de traducción
para cadenas