Automata de Pila

Capítulo 11.

Autómatas a pila
11.1. Concepto de AP
Definición, Representación, Lenguaje
reconocido, AP por vaciado de pila, AP
por estado final, AP determinista.

11.2. Equivalencia entre AP por vaciado
de pila y AP por estado final
11.3. AP y lenguajes independientes de
contexto
Obtener un AP para aceptar el lenguaje
generado por una GIC. Obtener una GIC
para generar ellenguaje aceptado por un
AP.

1

11.1. Concepto de Autómata a pila
Introducción
De igual manera que los lenguajes regulares se pueden
representar mediante autómatas finitos deterministas, los
lenguajes independientes del contexto tienen su correspondencia
en otro tipo de dispositivo: el Autómata a Pila (AP).
Un autómata a pila es un dispositivo que tiene acceso a:
• Una secuencia desímbolos de entrada, que en general se
representa por una cinta que se desplaza frente a un
mecanismo de captación de dichos símbolos.
• El símbolo superior de una memoria en pila (LIFO)
Un autómata a pila se encuentra en cada momento en un estado
determinado y el estado siguiente depende de los tres elementos
siguientes:
• estado actual
• símbolo de entrada
• símbolo superior de la pilaGeneralmente, el autómata a pila es no determinista en el
sentido de que se permite que haya varias acciones posibles en
cada momento.

2

Un AP puede realizar dos tipos de operaciones elementales:
1. Dependientes de la entrada.
Se lee la cinta y se avanza la cabeza lectora,
En función:
•

del estado actual (qi)

•

del símbolo leído en la cinta (a)

•

del símbolo en la cimade la pila (Z)

Se pasa a un nuevo estado, se elimina el elemento Z de la
cima de la pila y se introduce en su lugar una cadena de
símbolos.
2. Independientes de la entrada.
Las mismas operaciones que en el caso anterior, sólo que
no se lee la cinta, ni se avanza la cabeza lectora. Se
maneja la pila sin la información de entrada.

3

Definición formal de un AP
Un autómata a pilaes una séptupla:
AP= (Σ, Γ, Q, A0, q0, f, F)
donde :
1.
2.
3.
4.
5.
6.
7.

Σ es el alfabeto de entrada
Γ es el alfabeto de la pila
Q es un conjunto finito de estados
A0 ∈ Γ es el símbolo inicial de la pila
q0 ∈ Q el estado inicial del autómata
F ⊆ Q es el subconjunto de estados finales
f es una aplicación denominada función de transición
de ternas (estado, símbolo de entrada oλ, símbolo de
pila) en el conjunto de las partes Q×Γ*
f : Q×{Σ∪{λ}}× Γ → 2

Q×Γ*

(subconjunto finito)

Un AP comienza su funcionamiento en la configuración inicial:
•
en el estado inicial (q0)
•
con sólo un símbolo en la pila (A0)
•
con la cabeza lectora en el primer símbolo de la entrada
A partir de esta configuración realiza transiciones según la
definición de la función f.4

Interpretación de la función de transición
Representaremos con:
(a, b,...) los elementos de Σ
(A, B, C..) los de Γ
(x, y, z,...) los de Σ*
(X, Y, Z,...) los de Γ*
La interpretación de f es:
a)

f(q, a, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)}

cuando el autómata se encuentra en el estado q, lee el símbolo
de entrada a y tiene el símbolo A en la cima de la pila; el
autómatapasará a algún estado qi (recordar que es no
determinista), eliminará el símbolo A de la pila e introducirá en
ella la palabra Zi , quedando la cabeza de Zi en la cima de la
pila.
b)

f(q, λ, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)}

cuando el autómata se encuentra en el estado q, y tiene el
símbolo A en la cima de la pila; el autómata pasará a algún
estado qi (recordar que es nodeterminista), eliminará el símbolo
A de la pila e introducirá en ella la palabra Zi , quedando la
cabeza de Zi en la cima de la pila.
Se entiende que el resultado de la función f para las
configuraciones (estado, símbolo de entrada y símbolo de pila)
no explícitamente especificadas es el conjunto vacío. Estas
representan configuraciones “muertas” del autómata.

5

Representación gráfica...