Autómatas a Pila: Conceptos Clave, Funcionamiento y Estructura Formal

Autómatas a Pila: Definición, Funcionamiento y Lenguajes Aceptados

Pensemos en un lenguaje definido como L = {xⁿyⁿ | n ≥ 1}, donde ‘x’ es un paréntesis izquierdo e ‘y’ es un paréntesis derecho. No existe un autómata finito que pueda reconocer dicho lenguaje. Uno de los motivos por los que esto ocurre es que el autómata finito no tiene forma de recordar cuántas ‘x’ se detectaron en la primera parte de la cadena.

Un autómata a pila, se puede decir, es una extensión de los autómatas finitos al que se le agrega una funcionalidad de memorizar.

Una pila, en nuestro contexto, es una estructura de datos que nos permite almacenar y recuperar sus datos. El modo de acceso es del tipo LIFO (Last In, First Out – último en entrar, primero en salir).

Push	Esta operación inserta un elemento en la cima (top) de la pila.
Pop	Esta operación saca y elimina el último dato (la cima o top) de la pila.

Se puede decir que hay dos grupos de autómatas a pila: uno de los subgrupos es el de los autómatas finitos no deterministas con transiciones ε, y el otro es el de los autómatas a pila deterministas con transiciones ε.

Definición Informal de Autómata a Pila

Informalmente, un autómata a pila (o AP) es un autómata finito no determinista con transiciones ε, con el agregado de una pila. Esta pila permite almacenar datos, los llamados símbolos de pila de la máquina, de modo que, a diferencia de un autómata finito, el autómata a pila puede recordar una cantidad infinita de información.

Las transiciones que ejecuta este tipo de máquina deben ser variantes de la siguiente secuencia básica:

Leer un símbolo de la entrada;
Extraer un símbolo de la pila;
Insertar un símbolo en la pila;
Pasar a un nuevo estado.

(p, x, s, q, y)

Donde:

p: Es el estado actual.
x: Es el símbolo del alfabeto que se lee en la entrada.
s: Es el símbolo que se extrae de la pila.
q: Es el nuevo estado.
y: Es el símbolo que se inserta en la pila.

La notación anterior nos indica que el estado actual, el símbolo de entrada y el símbolo en la cima de la pila ayudan a determinar el nuevo estado y el símbolo que deberá insertarse en la pila.

Un autómata a pila es un modelo matemático que recibe una cadena constituida por símbolos de un alfabeto y determina si esa entrada (cadena o símbolo) pertenece al lenguaje que el autómata reconoce.

Componentes Principales de un Autómata a Pila:

Cuenta con un flujo de entrada (representado en la imagen como una cinta que contiene los símbolos a ingresar).
La cabeza lectora se desplaza en un solo sentido.
Posee un mecanismo de control que puede encontrarse en uno de los estados finitos. Uno de estos estados se designa como el inicial y, al menos uno, es el de aceptación.
Posee una estructura de datos para almacenar información que luego puede ser recuperada o recordada.

Definición Formal de Autómata a Pila

P = (Q, Σ, Γ, δ, q₀, Z₀, F)

Donde:

Q

Es un conjunto finito de estados.

Σ

Es un conjunto finito de símbolos de entrada.

Γ

Es el alfabeto de la pila, también finito.

δ

Es la función de transición. Esta controla el comportamiento del autómata. Formalmente, toma como argumento δ(q, a, X), donde:

q es un estado de Q.
a es cualquier símbolo de entrada de Σ o a = ε (la cadena vacía, la cual se supone no es un símbolo de entrada).
X es un símbolo de la pila, de modo que pertenece a Γ.

La salida de δ es un conjunto finito de pares (p, γ), donde p es el nuevo estado y γ es la cadena de símbolos de la pila que reemplaza X en la parte superior de la pila (o valor top).

q₀

Es el estado inicial. Es el estado en el que se encuentra el autómata antes de realizar ninguna operación.

Z₀

Es el símbolo inicial. La pila al iniciar consta de una instancia de este símbolo y de nada más.

F

Es el conjunto de estados de aceptación o estados finales.

Otra Definición Formal de Autómata a Pila

El lector puede encontrar otra formalidad que define al autómata a pila: una séxtupla (S, Σ, Γ, T, ι, F), donde:

S: Conjunto finito de los estados.
Σ: Alfabeto del autómata.
Γ: Conjunto finito de símbolos de la pila.
T: Es la función de transición (similar a δ).
ι: Es el estado inicial, pertenece a S.
F: Es la colección de estados aceptados o de aceptación, este es un subconjunto de S.

Los arcos corresponden a las transiciones del autómata a pila de la siguiente forma: para un arco con etiqueta (a, X/α) de un estado q a un estado p, indica que δ(q, a, X) contiene el par (p, α).

Es decir, la etiqueta del arco indica qué entrada se utiliza y también muestra los elementos situados en la cima de la pila.

Lo que no se representa en el diagrama de Figura 6 es el símbolo inicial.

Configuraciones y Movimiento de un Autómata a Pila

Se llama descripción instantánea o configuración de un autómata a pila a su situación en un momento dado, y se expresa formalmente mediante la terna:

(q, w, γ)

Donde:

q: Es el estado actual del autómata.
w: Es lo que queda de la entrada y que falta por analizar (w ∈ Σ*).
γ: Es el contenido de la pila en el instante actual. Si la pila está vacía, γ = ε.

El triplete (q, w, γ) es la descripción instantánea (ID) o configuración del autómata a pila.

Movimiento de un Autómata a Pila

Para los autómatas a pila necesitamos una notación que nos muestre los cambios en el estado, la entrada y la pila.

El movimiento de un autómata a pila es la transición entre dos ID, y se representa con el operador ⊢.

Sea P = (Q, Σ, Γ, δ, q₀, Z₀, F) un autómata a pila. Se define ⊢ como: