Un automa a stati finiti ha una memoria fissata. Se gli si aggiunge una pila illimitata, cioè una struttura in cui si può inserire e togliere solo l'elemento in cima, si ottiene l'automa a pila (pushdown automaton, PDA). È un'aggiunta piccola, ma sufficiente a riconoscere strutture annidate come parentesi, blocchi e chiamate di funzione. I PDA sono la controparte operativa delle grammatiche libere dal contesto, così come i DFA lo sono delle espressioni regolari.
La definizione
Un PDA è una sestupla (Q, Σ, Γ, δ, q₀, F), dove rispetto all'automa finito compaiono due novità:
- Γ è l'alfabeto della pila, che può contenere simboli diversi da quelli dell'input;
- la funzione di transizione δ: Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → P(Q × (Γ ∪ {ε})) guarda lo stato, il simbolo di input (o nessuno) e il simbolo in cima alla pila (o nessuno), e restituisce un insieme di coppie (nuovo stato, simbolo da mettere in cima).
Una transizione si scrive spesso come a, X → Y: «leggendo a, con X in cima alla pila, togli X e metti Y». Se X è ε non si toglie nulla; se Y è ε non si aggiunge nulla.
Nella versione standard il PDA è non deterministico e accetta se esiste un ramo di calcolo che consuma tutto l'input e termina in uno stato accettante.
Un esempio: aⁿbⁿ
Il PDA per {aⁿbⁿ : n ≥ 0} usa la pila come contatore:
- All'inizio mette sulla pila un marcatore di fondo, per esempio $.
- Per ogni a letta, mette una A sulla pila.
- Quando incontra la prima b, passa a uno stato in cui, per ogni b, toglie una A.
- Se alla fine dell'input in cima c'è di nuovo $, toglie il marcatore e passa allo stato accettante.
Se arrivano più b che a, a un certo punto la pila mostra $ quando servirebbe una A e il ramo muore. Se arrivano meno b, la pila contiene ancora qualche A e lo stato accettante non viene raggiunto. Se compare una a dopo una b, non esiste transizione e il ramo muore.
Un esempio che richiede non determinismo
Il linguaggio dei palindromi di lunghezza pari, {wwᴿ : w ∈ {a, b}*}, dove wᴿ è w scritta al contrario, si riconosce così:
- Si leggono i simboli e si mettono sulla pila.
- A un certo punto il PDA indovina di essere arrivato a metà e cambia stato.
- Da lì, ogni simbolo letto deve coincidere con quello in cima alla pila, che viene tolto.
- Si accetta se la pila torna vuota esattamente alla fine dell'input.
Il punto 2 è essenziale: leggendo da sinistra a destra non c'è modo di sapere dove sia la metà. Il non determinismo esplora tutte le possibilità e basta che una funzioni.
L'equivalenza con le grammatiche
Il risultato centrale è:
un linguaggio è libero dal contesto se e solo se è riconosciuto da un automa a pila non deterministico.
Le due direzioni hanno costruzioni concrete.
- Da grammatica a PDA: il PDA mette sulla pila la variabile iniziale. Se in cima c'è una variabile, sceglie in modo non deterministico una regola e la sostituisce con il lato destro. Se in cima c'è un terminale, lo confronta con l'input e lo toglie. Accetta quando input e pila finiscono insieme. In pratica simula una derivazione sinistra.
- Da PDA a grammatica: si costruisce una variabile Aₚq per ogni coppia di stati, che genera le stringhe capaci di portare il PDA da p a q lasciando la pila com'era. È la direzione più tecnica, ma l'idea è che ogni coppia «push e corrispondente pop» diventa una regola.
Deterministico non basta
A differenza degli automi finiti, per i PDA il non determinismo aggiunge potere. I PDA deterministici (DPDA), in cui a ogni passo è possibile al massimo una mossa, riconoscono una classe strettamente più piccola: i linguaggi liberi dal contesto deterministici.
Il linguaggio wwᴿ è un esempio di linguaggio libero dal contesto che non è deterministico. Se invece si inserisce un separatore al centro, come in {wcwᴿ}, il DPDA sa esattamente quando cambiare comportamento e il linguaggio diventa deterministico.
Questa distinzione ha conseguenze pratiche: i parser usati nei compilatori, come quelli LR e LL, sono sostanzialmente DPDA. Per questo i progettisti di linguaggi scrivono grammatiche che rientrino nella classe deterministica, in modo che l'analisi avvenga in tempo lineare senza tornare indietro.
Limiti dell'automa a pila
Anche la pila ha i suoi limiti: si può leggere solo la cima, e ciò che viene tolto è perso. Per questo un PDA non riconosce {aⁿbⁿcⁿ}: dopo aver usato la pila per confrontare le a con le b, non ne resta traccia per controllare le c. Per linguaggi di questo tipo serve un modello ancora più potente, come una macchina di Turing o un automa limitato linearmente.
In sintesi
- Un PDA è un automa finito con una pila illimitata, accessibile solo dalla cima.
- La pila permette di contare e di confrontare strutture annidate, come in aⁿbⁿ e nei palindromi.
- I PDA non deterministici riconoscono esattamente i linguaggi liberi dal contesto.
- I PDA deterministici sono strettamente più deboli, ma sono la base dei parser LL e LR.
- Un PDA non riconosce aⁿbⁿcⁿ: la pila non basta per confronti multipli.
