Automa a pila

Un automa a pila o (noto anche con la sigla PDA, dall'inglese pushdown automaton) è un tipo di macchina astratta, in particolare un automa la cui memoria di lavoro è costituita da una pila, una struttura dati i cui dati possono essere estratti in ordine necessariamente inverso rispetto a quello di inserimento.Un automa a pila è in grado di riconoscere ed accettare tutti i linguaggi che nella teoria delle grammatiche formali sono detti non contestuali, ovvero di tipo 2 secondo la classificazione gerarchica di Chomsky.