Autómatas con Pila: estructura y funcionamiento en informática

Introducción a los Autómatas con Pila

El Autómata con Pila (AP), en inglés Push Down Automata, es básicamente un autómata finito al que se le ha incorporado una memoria de pila. La memoria de pila o memoria LIFO (Last In First Out) incrementa la capacidad de resolver problemas del autómata finito convencional, al incorporarle la posibilidad de memorizar total o parcialmente la cadena leída y cualquier otra marca que ayude al procesamiento de la misma. Así, el AP dispone de registros de memoria que puede usar ventajosamente, aun a pesar de las limitaciones propias de las memorias LIFO. Como ya fue anticipado en el Capítulo 1, los autómatas con pila son capaces de reconocer lenguajes generados por gramáticas menos restringidas que las regulares: las gramáticas independientes de contexto o tipo 2. El hecho de que todos los lenguajes de computación respondan a este tipo de gramáticas hace que los AP sean muy estudiados y estén ampliamente difundidos como elementos centrales en los compiladores y en otras numerosas aplicaciones.

Una variante muy interesante del autómata con pila convencional es el Autómata con Pila Bidireccional (APB), que surge de incorporar memoria de pila en un AFDB como los estudiados en el Capítulo 3. A diferencia de lo que ocurre con éstos, los APB aumentan la capacidad de reconocimiento de los AP y pueden operar algunos lenguajes provenientes de gramáticas tipo 1. Además, la bidireccionalidad permite en muchos casos simplificar notablemente los diseños. Otro atractivo de los APB es la existencia de algoritmos muy eficientes para su simulación en computadoras, como es el de Cook.1

Autómatas con Pila Deterministas y No Deterministas

Agregarle una memoria de pila a un autómata finito convencional implica incorporarle dos nuevos componentes: el alfabeto de símbolos de la pila y, entre ellos, un símbolo especial destinado a servir de referencia, llamado marca de fondo de pila. Este último es necesario debido a la naturaleza de los accesos LIFO y con el fin de permitir comprobar si la pila ya está descargada.

Definición del AP

Tal cual lo anticipado, el autómata con pila es un autómata finito al que le fue incorporado una memoria LIFO. Por tal motivo, mantiene su alfabeto de entrada, conjunto de estados, estado inicial, estados de aceptación y función de transición. Luego a la definición se incorporan el alfabeto de pila y la marca de referencia, por lo que el AP es una séptupla. Se define:

ΑΡ = (ΣΕ, Γ, Q, qo, #, A, f )

donde:

ΣΕ : Alfabeto de símbolos de entrada Γ : Alfabeto de símbolos de la pila Q : Conjunto finito y no vacío, de estados posibles q0 : Estado inicial de operación, q0 € Q A : Conjunto de estados de aceptación, A c Q # : Símbolo de referencia de pila, # E Ty # ¢ LE f : Función de transición

Es indudable que, al incorporar una memoria de pila, es necesario prever su reconocimiento y operación por parte del autómata y esto debe ser contemplado en la función de transición. En el caso de un AP no determinista (APND), se trata de una relación, que toma la forma:

f. Q x (ΣΕ {}) x Γ > (Q xΓ*)

A partir de la observación de esta formulación, se deduce que:

1 "Lenguajes, gramáticas y autómatas", Rafael Cases Muñoz (Ref. Coo71, Pg. 219). GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 1Unidad 5: Autómatas con Pila

• El comportamiento del autómata en un intervalo de tiempo dado queda determinado por tres argumentos, que son: i) el estado actual, ii) el símbolo de entrada y iii) el símbolo leído de tope de la pila.
• A partir de estos tres argumentos, queda definido: i) el próximo estado del autómata y ii) la acción sobre la pila. Esta acción consiste en la grabación de varios símbolos, la de uno solo o de ninguno (A), y esto último corresponde al caso en que la pila es descargada, es decir, leída y no grabada. Además, el autómata moverá el cabezal sobre la cinta de entrada a la próxima posición de lectura.
• Las condiciones que hacen no determinista al AP definido son: i) que en un cierto intervalo de tiempo el APND puede operar sin leer la cadena de entrada (transición A), ii) que en algunos casos haya varias opciones de próximo estado y carga de pila, las que quedan agrupadas en un elemento del conjunto potencia P(Q × [*) y iii) una combinación de ambas condiciones.

En el caso del AP determinista (APD), la literatura presenta dos opciones para la definición de la función de transición. La primera surge al eliminar la transición A y admitir una sola condición de próximo estado y acción sobre la pila. La función queda definida entonces como:

f. Q xΣΕΧΓ -> Q xΓ*

La segunda definición posible de la función de transición del APD es la siguiente:

f: Q x (ΣΕ υ{})xΓ > Q x Γ*

con la condición que si f(q, A, b) está definida para qeQ y ber, entonces necesariamente no debe estarlo f(q, a, b) para todo a ΣΕ.

Representación de Autómatas con Pila

Como pudo observarse, la función de transición de los APD y APND tiene tres argumentos y esto imposibilita su representación mediante una tabla. Para casos en los que la cantidad de estados y la cantidad de símbolos de pila es poco numerosa, puede recurrirse a una tabla en la que cada fila corresponda a un elemento de Q x [ y cada columna a un elemento del alfabeto de entrada LE O 2. Además, para todos los casos sigue siendo válida la representación mediante grafos y ésta es la opción más utilizada. En estos casos, los arcos dirigidos son rotulados con una etiqueta a, b / a, donde aELE representa el símbolo de entrada leído, bel el símbolo leído del tope de pila y del* representa la cadena grabada sobre la pila, de tal forma que el último símbolo de misma quede en la cima de la pila. Las dos formas de representación, tabla y grafo serán utilizadas en los ejemplos que se presentan en este capítulo.

Concepto de Configuración o Descripción Instantánea

Al igual que en los AF, es necesario definir la condición en la que se encuentra un autómata con pila en un intervalo de tiempo t dado y, para ello, se recurre a la descripción instantánea o configuración:

Kt = ( q , ß, 8)

donde q representa el estado en que se encuentra el AP, ß la subcadena de entrada pendiente de ser leída y 8 el contenido de la pila. A partir de esta definición y ante una cadena de entrada a, tal que de ZE*, se puede reconocer la configuración inicial como:

Ko = ( qo , a , # )

De igual forma, se define la configuración final como:

Kn = (q, 1,8)

donde la cadena debe haber sido completamente leída. En este caso, las condiciones a ser cumplidas por el estado q y el contenido de la pila 8 son diversas y se especifican en el siguiente apartado.

GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 2Unidad 5: Autómatas con Pila

El tránsito de una configuración a otra es también aquí denominado movimiento, es decir que si existe la transición f(p, a, b) = (q, bb), el movimiento del estado p al q, leyendo el símbolo de entrada a, extrayendo de la cima de la pila el símbolo de pila b y almacenando en la pila la cadena bb, queda representado como:

( p , aß, ob ) | ( q , ß, öbb )

y el movimiento desde la configuración inicial a la final es representado:

( qo, a, # ) |* ( q, 1, 8)

donde * representa una cantidad finita de movimientos.

Por último, y tal como ocurrió con los AFD y APND, el comportamiento de los autómatas con pila ante una cierta cadena de entrada queda convenientemente representado por los árboles de configuraciones o descripciones instantáneas.

Aceptación de Lenguajes por Autómatas con Pila

Se admite que hay varias formas de aceptación de lenguajes por parte de los autómatas con pila. En todos los casos, las sentencias de los lenguajes deben conducir al autómata con pila desde su configuración inicial hasta su configuración final, y la diferencia está en las condiciones que definen la configuración final de aceptación, que son las siguientes:

1. Aceptación por vaciado de pila L = {a / (go, a, #) | * (q, λ, #) con go, qEQ, ΔΕΣΕ', #ΕΓ}
2. Aceptación por estado de aceptación L = {a / (qo, a, #) | * (q, λ. δ) con goEQ, qEA, αεΣΕ', δεΓ', #ΕΓ}
3. Aceptación por vaciado de pila y estado de aceptación L = {a / (go, a, #) | * (q, λ, #) con go, qEQ, qEA, ΔΕΣΕ', #ΕΓ}

Nótese que en todos los casos la sentencia ha sido completamente leída y la exigencia o no de pila vacía distinguirá dos tipos característicos de problemas que serán estudiados a través de los ejemplos presentados en lo que sigue.

No Equivalencia de APD y APND

Los Autómatas con Pila No Deterministas (APND) no tienen necesariamente Autómatas con Pila Deterministas (APD) equivalentes que acepten los mismos lenguajes. Es muy importante notar que esta falta de equivalencia no significa que no pueda existir un autómata con pila determinista que acepte una cadena específica del lenguaje, pero se trataría de una equivalencia muy restringida que carecería de generalidad. En los Ejemplos 5.1 y 5.2, se ilustra este problema.

AP Deterministas y Transiciones A

Al estudiarse los autómatas finitos en el Capítulo 3, se dijo que, por tratarse de máquinas abstractas, se prescindía de la técnica de implementación del medio de entrada y se utilizaba el concepto genérico de una cinta de entrada y su correspondiente cabezal. Es decir que se admite que la máquina es capaz de reconocer el momento en el que ha completado la lectura de una cadena, sin necesidad de precisar el modo en el que lo hace.

El autómata con pila es una evolución del autómata finito y el razonamiento anterior, en cuanto al reconocimiento de que una cadena de entrada ha sido completamente leída, es igualmente válido. Sin embargo, el autómata con pila utiliza también en su operación un tercer argumento, que es el símbolo presente en el tope de la pila (memoria LIFO), y dos de las condiciones de aceptación de sentencias requieren que la pila se encuentre tal como estaba al comenzar la máquina a operar (ver Aceptación de lenguajes). Esta situación se identifica como de pila vacía y, para ello, el AP incluye en su definición un símbolo de su alfabeto de pila que es explícitamente declarado marca del fondo de la pila (#) y que permite identificar esta condición. Por este motivo, una vez que el AP ha completado la lectura de una sentencia, debe verificarse que la pila se encuentra vacía y la única forma es leerla y comprobar que el símbolo GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 3