Gramáticas e Autómatos de Pilha

O Pumping Lemma aplicado à linguagem $E= \set{a^mb^m \st m \geq 0}$ 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.