Apunte Te Rico 3

UNIDAD TEMÁTICA III - Autómatas Pushdown y Lenguajes Libres de Contexto
En esta Unidad se estudiarán las Gramáticas Libres de Contexto, de tipo 2, y los autómatas que
reconocen los lenguajes generados por ellas, los Autómatas Push-Down –también conocidos como
Autómatas a Pila–. Este tipo de gramáticas y autómatas son importantes desde el punto de vista de la
Informática, debido a que permiten ladescripción de la mayoría de los lenguajes de programación, por lo
que posibilitan la construcción de compiladores.
♦ AUTÓMATAS PUSH-DOWN
 

1. Introducción
✁

Los Autómatas Push-Down son los autómatas más importantes entre las máquinas de estados finitos y
las de Turing. Su operación está íntimamente relacionada con muchos procesos computacionales, en
especial con el análisis y la traducción delenguajes artificiales.
Estos autómatas permiten analizar strings para reconocer si pertenecen o no a lenguajes de tipo 2, libres
de contexto. Tienen una estructura similar a la de los Autómatas Finitos, pero se les agrega una pila
(memoria auxiliar) para poder almacenar información que podrá ser útil en momentos posteriores del
análisis. Por ejemplo, en el caso de muchas gramáticas de lenguajes deprogramación existe la posibilidad
de utilizar paréntesis y estos deben estar balanceados (por cada paréntesis de apertura debe existir
posteriormente un paréntesis de cierre). Este aspecto es imposible de controlar con una Gramática Regular
(de tipo 3) debido a que, como no se conoce de antemano el número de paréntesis, se necesitarían infinitos
estados para llevar la cuenta de los paréntesis deapertura que se han leído para poder saber luego si todos
se cerraron o no. Los Autómatas Push-Down, al disponer de la memoria auxiliar (pila), pueden introducir en
ella un elemento por cada paréntesis de apertura leído, e ir eliminando de la pila un elemento por cada
paréntesis de cierre leído, y , así, llevar el control de si se han cerrado todos o no.
En la siguiente figura se muestra elesquema de este tipo de autómatas. Se dispone como entrada de
una cinta con los símbolos que forman el string que hay que analizar. El autómata tiene un cabezal de
lectura posicionado en cada momento en un símbolo de entrada; este cabezal sólo puede moverse hacia la
derecha y termina de moverse cuando llega al final de la cinta. Además, este tipo de autómatas, como los
anteriores, lleva el control delestado en el que está mediante una unidad de control de estados. Por último,
cuenta con una cinta de almacenamiento (pila), sobre la cual opera un cabezal de lectura-escritura.

Figura 1: Aceptor "Push-Down" en la Configuración (q, ϕ, σ)
La máquina comienza con la cinta de almacenamiento completamente en blanco (# en cada segmento),
escribe un símbolo en esta cinta cada vez que mueve su cabezal dealmacenamiento hacia la derecha, y lee
un símbolo desde esta cinta de almacenamiento cada vez que mueve el cabezal de almacenamiento hacia
la izquierda. Toda información que se encuentre a la derecha de este cabezal es irrecuperable, ya que será
sobre-escrita cuando el cabezal se mueva hacia la derecha.
Dado que el string escrito en la cinta de almacenamiento, que puede ser infinitamente largo,afecta el
comportamiento del autómata, es necesario que el aceptor Push-Down tenga una memoria ilimitada. Sin
embargo, la información más recientemente escrita debe ser la primera en ser recuperada. Este mecanismo
de acceso limitado a lo que se encuentra almacenado, es muy común en la práctica computacional y se
conoce como una pila "Push-Down" debido a que tiene como regla de recuperación lasiguiente: "último en
entrar, primero en salir" ("Last In, First Out").

1.1. Aceptores Push-Down. Definiciones
✂

Definición 1: Un aceptor Push-Down (APD) es una tupla de seis elementos:
M = (Q, S, U, P, Ι, F)
en la cual:
Q es el conjunto finito de estados de la unidad de control
S
es el alfabeto finito de entrada
U es el alfabeto finito de la pila o "stack"
P
es el programa de M
Ι ⊆ Q es el...