Capı́tulo 5

Autómatas de Pila

Puesto que los autómatas finitos no son suficientemente poderosos para aceptar los LLC,
1
cabe preguntarnos qué tipo de autómata se necesitarı́a para aceptar los LLC.

Una idea es agregar algo a los AF de manera que se incremente su poder de cálculo.

Para ser más concretos, tomemos por ejemplo el lenguaje de los paréntesis bien balancea-
dos, que sabemos que es propiamente LLC. 2 ¿Qué máquina se requiere para distinguir las
palabras de paréntesis bien balanceados de las que tienen los paréntesis desbalanceados?
Una primera idea podrı́a ser la de una máquina que tuviera un registro aritmético que le
permitiera contar los paréntesis; dicho registro serı́a controlado por el control finito, quien le
mandarı́a sı́mbolos I para incrementar en uno el contador y D para decrementarlo en uno. A
su vez, el registro mandarı́a un sı́mbolo Z para indicar que está en cero, o bien N para indicar
que no está en cero. Entonces para analizar una palabra con paréntesis lo que harı́amos serı́a
llevar la cuenta de cuántos paréntesis han sido abiertos pero no cerrados; en todo momento
dicha cuenta debe ser positiva o cero, y al final del cálculo debe ser exactamente cero. Por
ejemplo, para la palabra (())() el registro tomarı́a sucesivamente los valores 1, 2, 1, 0, 1, 0.
Recomendamos al lector tratar de diseñar en detalle la tabla describiendo las transiciones
del autómata.

Como un segundo ejemplo, considérese el lenguaje de los palı́ndromos (palabras que se

leen igual al derecho y al revés, como ANITALAVALATINA). Aquı́ la máquina contadora
no va a funcionar, porque se necesita recordar toda la primera mitad de la palabra para
poder compararla con la segunda mitad. Más bien pensarı́amos en una máquina que tuviera
la capacidad de recordar cadenas de caracteres arbitrarias, no números. Siguiendo esta idea,
podrı́amos pensar en añadir al AF un almacenamiento auxiliar, que llamaremos pila, donde
se podrán ir depositando caracter por caracter cadenas arbitrariamente grandes, como se
aprecia en la figura 5.1. A estos nuevos autómatas con una pila auxiliar los llamaremos
1
¡Cuidado! Esto no impide que un LLC en particular pueda ser aceptado por un AF, cosa trivialmente
cierta si tomamos en cuenta que todo lenguaje regular es a la vez LLC.
2
“Propiamente LLC” quiere decir que el lenguaje en cuestión es LLC pero no regular.

145
146 CAPÍTULO 5. AUTÓMATAS DE PILA

b a a b a b

a
a
q0
q1

q2

q3

Figura 5.1: Autómata con una pila auxiliar

Autómatas de Pila, abreviado AP.

5.1. Funcionamiento de los Autómatas de Pila (infor-

mal)

La pila funciona de manera que el último caracter que se almacena en ella es el primero
en salir (“LIFO” por las siglas en inglés), como si empiláramos platos uno encima de otro, y
naturalmente el primero que quitaremos es el último que hemos colocado. Un aspecto crucial
de la pila es que sólo podemos modificar su “tope”, que es el extremo por donde entran o
salen los caracteres. Los caracteres a la mitad de la pila no son accesibles sin quitar antes
los que están encima de ellos.

La pila tendrá un alfabeto propio, que puede o no coincidir con el alfabeto de la palabra de
entrada. Esto se justifica porque puede ser necesario introducir en la pila caracteres especiales
usados como separadores, según las necesidades de diseño del autómata.

Al iniciar la operación de un AP, la pila se encuentra vacı́a. Durante la operación del

AP, la pila puede ir recibiendo (y almacenando) caracteres, según lo indiquen las transiciones
ejecutadas. Al final de su operación, para aceptar una palabra, la pila debe estar nuevamente
vacı́a.

En los AP las transiciones de un estado a otro indican, además de los caracteres que se
consumen de la entrada, también lo que se saca del tope de la pila, asi como también lo que
se mete a la pila.

Antes de formalizar los AP, vamos a utilizar una notación gráfica, parecida a la de los
diagramas de los autómatas finitos, como en los AP de las figuras 5.2 (a) y (b). Para las
transiciones usaremos la notación “w/α/β”, donde w es la entrada (secuencia de caracteres)
que se consume, α es lo que se saca de la pila, y β lo que se mete a la pila.

Por ejemplo, la transición “a/ε/b” indica que se consume de la entrada un caracter a, no

5.2. DISEÑO DE AP 147

se saca nada de la pila, y se mete b a la pila. Se supone que primero se ejecuta la operación
de sacar de la pila y luego la de meter.

Al igual que los AF, los AP tienen estados finales, que permiten distinguir cuando una
palabra de entrada es aceptada.

De hecho, para que una palabra de entrada sea aceptada en un AP se deben cumplir
todas las condiciones siguientes:

1. La palabra de entrada se debe haber agotado (consumido totalmente).

2. El AP se debe encontrar en un estado final.

3. La pila debe estar vacı́a.

5.2. Diseño de AP

El problema de diseño de los AP consiste en obtener un AP M que acepte exactamente

un lenguaje L dado. Por exactamente queremos decir, como en el caso de los autómatas
finitos, que, por una parte, todas las palabras que acepta efectivamente pertenecen a L, y
por otra parte, que M es capaz de aceptar todas las palabras de L.

Aunque en el caso de los AP no hay metodologı́as tan generalmente aplicables como era
el caso de los autómatas finitos, siguen siendo válidas las ideas básicas del diseño sistemático,
en particular establecer claramente qué es lo que “recuerda” cada estado del AP antes de
ponerse a trazar transiciones a diestra y siniestra. Para los AP, adicionalmente tenemos que
establecer una estrategia clara para el manejo de la pila.

En resumen, a la hora de diseñar un AP tenemos que repartir lo que requiere ser “recor-
dado” 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

an bn , para cualquier número natural n.

Una idea que surge inmediatamente es la de utilizar la pila como “contador” para recordar
la cantidad de a’s que se consumen, y luego confrontar con la cantidad de b’s. Una primera
versión de este diseño utiliza un sólo estado q, con transiciones a/ε/a y b/a/ε de q a sı́ mismo,
como en la figura 5.2(a).

Para verificar el funcionamiento del autómata, podemos simular su ejecución, listando

las situaciones sucesivas en que se encuentra, mediante una tabla que llamaremos “traza de
ejecución”. Las columnas de una traza de ejecución para un AP son: el estado en que se
148 CAPÍTULO 5. AUTÓMATAS DE PILA

a/ ε/a
a/ ε/a b/a/ ε
b/a/ ε

q q1 q2
b/a/ ε

(a) Incorrecto (b) Correcto

Figura 5.2: AP para el lenguaje an bn

encuentra el autómata, lo que falta por leer de la palabra de entrada, y el contenido de la

pila.

Por ejemplo, la traza de ejecución del AP del último ejemplo, para la palabra aabb, se
muestra a continuación: 3

Estado Por leer Pila

q aabb ε
q abb a
q bb aa
q b a
q ε ε

Concluı́mos que el AP efectivamente puede aceptar palabras como an bn . Sin embargo, hay
un problema: ¡el AP también acepta palabras como abab, que no tienen la forma deseada! (es
fácil construir la traza de ejecución correspondiente para convencerse de ello). El problema
viene de que no hemos recordado cuando se terminan las a y principian las b, por eso ha sido
posible mezclarlas en abab. Una solución es utilizar los estados para memorizar las situaciones
de estar consumiendo a o estar consumiendo b. El diagrama de estados correspondiente se
muestra en la figura 5.2(b).

Ejemplo.- Proponer un AP que acepte el lenguaje de los palı́ndromos con un número

par de sı́mbolos, esto es, palabras que se leen igual de izquierda a derecha y de derecha a
izquierda, y que tienen por tanto la forma wwR , donde wR es el reverso de w (esto es, invertir
el orden), en el alfabeto {a, b}. Por ejemplo, las palabras abba, aa y bbbbbb pertenecen a este
lenguaje, mientras que aab y aabaa no.

Una estrategia de solución para diseñar este AP serı́a almacenar en la pila la primera
mitad de la palabra, y luego irla comparando letra por letra contra la segunda mitad. Ten-
drı́amos dos estados s y f , para recordar que estamos en la primera o segunda mitad de la
palabra. En la figura 5.2 se detalla este AP.
3
Suponemos que el tope de la pila está del lado izquierdo, aunque en este ejemplo da lo mismo.
5.2. DISEÑO DE AP 149

b/ ε /b a/a/ ε
a/ ε/a b/b/ ε

s f
ε/ε/ε

Figura 5.3: AP para el lenguaje {wwR }

Se puede apreciar en el AP de dicha figura la presencia de una transición de s a f , en que

ni se consumen caracteres de la entrada, ni se manipula la pila. Esta transición parece muy
peligrosa, porque se puede “disparar” en cualquier momento, y si no lo hace exactamente
cuando hemos recorrido ya la mitad de la palabra, el AP podrá llegar al final a un estado
que no sea final, rechazando en consecuencia la palabra de entrada. Entonces, ¿cómo saber
que estamos exactamente a la mitad de la palabra?

Conviene en este punto recordar que en un autómata no determinista una palabra es

aceptada cuando existe un cálculo que permite aceptarla, independientemente de que un
cálculo en particular se vaya por un camino erróneo. Lo importante es, pues, que exista un
cálculo que acepte la palabra en cuestión. Por ejemplo, la siguiente tabla muestra un cálculo
que permite aceptar la palabra w = abba:

Estado Falta leer Pila Transición

s abba ε
s bba a 1
s ba ba 2
f ba ba 3
f a a 5
f ε ε 4

5.2.1. Combinación modular de AP

En los AP también es posible aplicar métodos de combinación modular de autómatas,

como hicimos con los autómatas finitos. En particular, es posible obtener AP que acepten la
unión y concatenación de los lenguajes aceptados por dos AP dados.

En el caso de la unión, dados dos AP M1 y M2 que aceptan respectivamente los lenguajes

L1 y L2 , podemos obtener un AP que acepte la unión L1 ∪L2 , introduciendo un nuevo estado
inicial s0 con transiciones ε/ε/ε a los dos antiguos estados iniciales s1 y s2 , como se ilustra
en la figura 5.4. 4
4
El procedimiento de combinación de AP para obtener la unión de autómatas puede ser descrito en forma
más precisa utilizando la representación formal de los AP, que se estudia en la siguiente sección; sin embargo,
hacer esto es directo, y se deja como ejercicio (ver sección de ejercicios).
150 CAPÍTULO 5. AUTÓMATAS DE PILA












































































































































F





































































1







































s




































1



















































ε/ε/ε 









































s0



 


 


 


 


 


 


 


 


 


 


 


 
ε/ε/ε 





 


 


 


 


 


 


 


 


 


 


 



 


 


 


 


 


 


 


 


 


 


 


 






 s


 


 


 


 


 


 F


 


 


 


 
2




 


 


 


 


 


 


 


 


 


 


 


 
2



 
 
 
 
 
 
 
 
 
 
 
Figura 5.4: Unión de AP

Ejemplo.- Obtener un AP que acepte el lenguaje {an bm |n 6= m}. Claramente este lenguaje
es la unión de {an bm |n > m} con {an bm |n < m}, por lo que basta obtener los AP de cada
uno de ellos, y combinarlos con el método descrito.

Ejemplo.- Diseñar un AP que acepte el lenguaje L = {ai bj ck |¬(i = j = k)}. Nos damos
cuenta de que L es la unión de dos lenguajes, que son:

L = {ai bj ck |i 6= j} ∪ {ai bj ck |j 6= k}

Para cada uno de estos dos lenguajes es fácil obtener su AP. Para el primero de ellos, el AP
almacenarı́a primero las a’s en la pila, para luego ir descontando una b por cada a de la pila;
las a’s deben acabarse antes de terminar con las b’s o bien deben sobrar a’s al terminar con
las b’s; las c’s no modifican la pila y simplemente se verifica que no haya a o b después de la
primera c. Dejamos los detalles como ejercicio para el lector.

También es posible obtener modularmente un AP que acepte la concatenación de los

lenguajes aceptados por dos AP dados. De hecho ya vimos en el capı́tulo 4 que la unión de
dos lenguajes libres de contexto es también libre de contexto, pues tiene una gramática libre
de contexto.

Sin embargo, la construcción de un AP que acepte la concatenación de dos lenguajes a

partir de sus respectivos AP M1 y M2 , es ligeramente más complicada que para el caso de la
unión. La idea básica serı́a poner transiciones vacı́as que vayan de los estados finales de M1
al estado inicial de M2 . Sin embargo, existe el problema: hay que garantizar que la pila se
encuentre vacı́a al pasar de M1 a M2 , pues de otro modo podrı́a resultar un AP incorrecto.
Para esto, es posible utilizar un caracter especial, por ejemplo “@”, que se mete a la pila
antes de iniciar la operación de M1 , el cual se saca de la pila antes de iniciar la operación de
M2 . Los detalles se dejan como ejercicio (ver sección de ejercicios).
5.3. FORMALIZACIÓN DE LOS AP 151

5.3. Formalización de los AP

Un autómata de pila 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

s ∈ K es el estado inicial

F ⊆ K es un conjunto de estados finales,

∆ ⊆ (K × Σ∗ × Γ∗ ) × (K × Γ∗ ) es la relación de transición.

Ahora describiremos el funcionamiento de los AP. Si tenemos una transición de la forma

((p, u, β), (q, γ)) ∈ ∆, el AP hace lo siguiente:

Estando en el estado p, consume u de la entrada;

Saca β de la pila;

Llega a un estado q;

Mete γ en la pila

Las operaciones tı́picas en las pilas –tı́picamente llamadas en inglés el “push” y el “pop”–
pueden ser vistas como casos particulares de las transiciones de nuestro AP; en efecto,
si sólo queremos meter la cadena γ a la pila, se harı́a con la transición ((p, u, ε), (q, γ))
(“push”), mientras que si sólo queremos sacar caracteres de la pila se hará con la transición
((p, u, β), (q, ε)) (“pop”).

Ahora formalizaremos el funcionamiento de los AP, para llegar a la definición del lenguaje
aceptado por un AP. Para ello seguiremos el mismo método que usamos en el caso de los
AF, método que reposa completamente en la noción de configuración.

Definición.- Una configuración es un elemento de K × Σ∗ × Γ∗ .

Por ejemplo, una configuración podrı́a ser [[q, abbab, ⊗aa#a]] –obsérvese que seguimos
la misma notación que para representar las configuraciones de los AF. Puede verse que las
transiciones se definen como una relación, no como una función, por lo que de entrada se les
formaliza como autómatas no deterministas.

Ahora definimos la relación ` entre configuraciones de la manera siguiente:

152 CAPÍTULO 5. AUTÓMATAS DE PILA

Definición.- Sea M = (K, Σ, Γ, ∆, s, F ) un AP, entonces [[p, ux, βα]]| `M [[q, x, γα]] ssi
existe ((p, u, β), (q, γ)) ∈ ∆. En general vamos a omitir el subı́ndice de `M , quedando sim-
plemente como `. La cerradura reflexiva y transitiva de ` es `∗ .

Definición.- Un AP M = (K, Σ, Γ, ∆, s, F ) acepta una palabra w ∈ Σ∗ ssi [[s, w, ε]] `∗M

[[p, ε, ε]], donde p ∈ F . L(M ) es el conjunto de palabras aceptadas por M .

Ejemplo.- Formalizar el AP de la figura 5.2, que acepta el lenguaje {wwR }, w ∈ {a, b}.

Solución.- El AP es el séxtuplo (K, Σ, Γ, ∆, s, F ), donde

K = {s, f }, F = {f }, Σ = {a, b, c}, Γ = {a, b}

∆ está representada en la siguiente tabla:

(s, a, ε) (s, a)
(s, b, ε) (s, b)
(s, ε, ε) (f, ε)
(f, a, a) (f, ε)
(f, b, b) (f, ε)

5.4. Relación entre AF y AP

Teorema.- Todo lenguaje aceptado por un AF es también aceptado por un AP

Este resultado debe quedar intuitivamente claro, puesto que los AP son una extensión
de los AF.

Prueba: Sea (K, Σ, ∆, s, F ) un AF; el AP (K, Σ, ∅, ∆0 , s, F ), con ∆0 = {((p, u, ε), (q, ε)) |
(p, u, q) ∈ ∆} acepta el mismo lenguaje.

5.5. Relación entre AP y LLC

Ahora vamos a establecer el resultado por el que iniciamos el estudio de los AP, es decir,
verificar si son efectivamente capaces de aceptar los LLC.

Teorema.- Los autómatas de pila aceptan exactamente los LLC.

Vamos a examinar la prueba de esta afirmación, no solamente por el interés por la rig-
urosidad matemática, sino sobre todo porque provee un método de utilidad práctica para
transformar una GLC en un AP. La prueba de este teorema se puede dividir en dos partes: