Autómatas de Pila: Funcionamiento, Definición y Teorema de Equivalencia con Autómatas Finitos Deterministas

Autómatas de Pila

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

1. Incrementar la cima.
2. Insertar datos.

Para extraer datos, se utiliza el procedimiento POP:

1. Extraer dato.
2. 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:

1. 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 (#).
2. 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.
3. Introduzca la transición (+, ε, ε : p, #).
4. Introduzca la transición (p, ε, ε : q, S), donde S es el axioma de la gramática.
5. Introduzca la transición de la forma (q, ε, N : q, W).
6. 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.
7. 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.