Gramáticas e Autómatos de Pilha

O Pumping Lemma aplicado à linguagem $E=\left\{a^m{b}^m:m\ge 0\right\}$ mostra que as linguagens regulares não são adequadas para definir linguagens de programação.

Portanto, é necessária outra abordagem para resolver o Problema Principal de ALP — Dada uma linguagem $A$ e uma palavra $p$ no mesmo alfabeto, determinar se $p\in A$ de forma computável, acessível e adequada.

Neste capítulo definem-se certas gramáticas formais que generalizam as linguagens regulares e estão associadas aos autómatos de pilha, uma forma simples de autómato com memória ilimitada.