Autómata ampliado con una pila LIFO que actúa como memoria auxiliar no acotada; reconoce exactamente los lenguajes que generan las gramáticas libres de contexto (lenguajes context‑free) mediante transiciones de estado junto con operaciones de push y pop en la pila.

Principio

Un control de estado finito combinado con una pila LIFO proporciona memoria estructurada y no acotada que permite capturar dependencias anidadas y jerárquicas manteniendo una estructura de transición de estados finitos.

Demostración

Un autómata con pila no determinista que, para la entrada a^n b^n, apila un símbolo por cada a y luego desapila uno por cada b acepta precisamente el lenguaje balanceado {a^n b^n | n≥0} por criterio de pila vacía o estado de aceptación.

Aplicación incorrecta

Usar un autómata con pila para reconocer lenguajes que requieren dos contadores independientes (por ejemplo a^n b^n c^n) o suponer que PDA deterministas (DPDA) pueden decidir todos los lenguajes libres de contexto; confundir características prácticas de parsers (lookahead, acciones semánticas) con el modelo formal de PDA.

Consecuencia

Su uso correcto implica equivalencias formales (con gramáticas libres de contexto y PDAs no deterministas), es la base de algoritmos de análisis sintáctico y define fronteras de decidibilidad (pertenencia, vaciado en la clase CFL), y establece una separación clara de autómatas regulares y modelos de potencia de Turing.

Inversión

Un autómata finito carece de pila y por tanto no puede imponer dependencias anidadas no acotadas; una máquina de Turing sustituye la pila por una cinta bidireccional no acotada, aumentando la potencia expresiva más allá de los PDA.

Límite

Alcance: autómatas con pila de pila única (aplican distinciones determinista vs no determinista); quedan excluidas las extensiones con múltiples pilas o colas, anotaciones temporales o probabilísticas y pilas con tokens distinguibles salvo indicación contraria.

Tensión semántica

Tensión entre el PDA teórico (pila única pura) y las implementaciones prácticas de parsers que añaden lookahead, acciones semánticas o pilas múltiples; también entre PDAs deterministas (clase más restringida) y no deterministas (clase CFL completa).

Síntesis

Un autómata con pila es un controlador de estados finitos provisto de una pila LIFO cuyas operaciones de push/pop permiten reconocer estructuras anidadas y context‑free que los autómatas finitos no pueden capturar.