Autómatas de pila: definición y equivalencia con los AFD

Resumen

El texto explica qué es un autómata de pila: un autómata con una pila como memoria, que usa las operaciones PUSH y POP. Presenta la notación de sus transiciones, su definición formal y el método de las tres columnas para seguir su funcionamiento. Después expone el teorema que afirma que para cada AFD existe un autómata de pila equivalente, con la idea de su demostración. El estudiante aprende la definición formal y la idea de la demostración.

Puntos clave

Un autómata de pila usa una pila como memoria. PUSH inserta datos en la cima y POP extrae el dato de la cima.
Cada transición se escribe (p, x, s : q, y): estado actual, símbolo leído, símbolo extraído de la pila, estado siguiente y símbolo insertado en la pila.
La definición formal incluye los estados Q, el alfabeto Σ, los símbolos de pila Γ, las transiciones δ, el estado inicial q0 y los estados de aceptación F.
El teorema de equivalencia afirma que para cada AFD existe un autómata de pila equivalente.
La demostración parte de una gramática que representa el AFD. Usa los estados t, p, q y f, siendo f el único estado de aceptación.
El método de las tres columnas muestra el contenido de la pila, el resto de la cadena de entrada y la transición usada en cada paso.

Ponte a prueba

Autómatas de Pila

Un autómata de pila utiliza como memoria una pila de datos. Para insertar datos, utiliza un procedimiento llamado PUSH:

Incrementar la cima.
Insertar datos.

Para extraer datos, se utiliza el procedimiento POP:

Extraer dato.
Decrementar la cima.

Definición

Al igual que un AFD (Autómata Finito Determinista), un autómata de pila cuenta con un flujo de entrada y un mecanismo de control que puede encontrarse en uno de un número finito de estados, con al menos uno de ellos siendo un estado de aceptación. La principal diferencia es que ahora se cuenta con un lugar donde guardar información para recuperarla más tarde. Los símbolos que pueden almacenarse se llaman símbolos de pila y son un conjunto finito que puede incluir el alfabeto de la máquina, los símbolos auxiliares y la marca de pila vacía.

Este proceso se representa con la notación (p, x, s : q, y), donde:

p: Estado actual.
x: Símbolo que se lee de la cadena de entrada.
s: Símbolo que se extrae de la pila.
q: Estado al que se pasa.
y: Símbolo que se inserta en la pila.

Definición Formal

Un autómata de pila es una séxtupla de la forma (Q, Σ, Γ, δ, q₀, F), donde:

Q: Conjunto de estados.
Σ: Alfabeto de la máquina.
Γ: Conjunto de símbolos de pila.
δ: Conjunto de transiciones.
q₀: Estado inicial.
F: Conjunto de estados de aceptación.

Teorema de Equivalencia entre Autómatas de Pila y Autómatas Finitos Deterministas

Teorema: Para cada AFD existe un autómata de pila equivalente.

Demostración: Dada una gramática G que representa un AFD, construimos un autómata de pila de la siguiente forma:

Designe el alfabeto igual al del autómata finito y los símbolos de pila como los terminales y auxiliares de G, agregando el símbolo pragma (#).
Designe los estados del autómata como t, p, q, f, donde t es el estado inicial y f es el único estado de aceptación.
Introduzca la transición (+, ε, ε : p, #).
Introduzca la transición (p, ε, ε : q, S), donde S es el axioma de la gramática.
Introduzca la transición de la forma (q, ε, N : q, W).
Introduzca la transición de la forma (q, x, x : q, ε) para cada terminal x de G, es decir, para cada símbolo del alfabeto.
Introduzca la transición (q, ε, # : f, ε).

Método de las Tres Columnas

Este método se utiliza para representar el funcionamiento del autómata de pila. Las tres columnas representan:

Contenido de la pila.
Resto de la cadena de entrada.
Transición utilizada.

Preguntas frecuentes

¿Qué diferencia hay entre un AFD y un autómata de pila?

Ambos tienen un flujo de entrada y un control con un número finito de estados. El autómata de pila añade un lugar donde guardar información para recuperarla más tarde, que es la pila.

¿Qué dice el teorema de equivalencia entre autómatas de pila y AFD?

Dice que para cada AFD existe un autómata de pila equivalente. La demostración construye el autómata a partir de una gramática que representa el AFD.