Automi a pila

Una volta introdotta la classe dei linguaggi context-free, generati dalle CFG, si vuole individuare un modello che permetta di riconoscere tali linguaggi. I riconoscitori trattati finora, cioè gli automi a stati finiti (in tutte le loro varianti), non sono adeguati a questo scopo, poichè si è visto che esistono linguaggi context-free, come ad esempio quello dei palindromi, che non sono regolari, ovvero non sono riconoscibili da automi a stati finiti. L’idea che consente di definire un modello più “potente” è quella di eliminare uno dei grossi vincoli degli automi a stati finiti: la quantità di memoria finita. A tale scopo, si estendono gli automi a stati finiti con una memoria esterna potenzialmente infinita. Tuttavia, perchè sia possibile riconoscere esattamente i linguaggi context-free, bisogna imporre su tale memoria una politica di accesso LIFO, Last In First Out, cioè la memoria deve essere uno stack, una pila, nella quale si può manipolare solo l’elemento in cima. Il modello risultante è definito formalmente in seguito.

Un automa a pila (PDA, PushDown Automation) è una settupla

$$ P = \lang Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\rang $$

in cui:

• $Q$ è un insieme finito e non vuoto di stati
• $\Sigma$ è l’alfabeto di input
• $\Gamma$ è l’alfabeto di stack
• $q_0 \in Q$ è lo stato iniziale
• $Z_0 \in \Gamma$ è il simbolo iniziale di stack
• $F\subseteq Q$ è l’insieme degli stati finali
• $\delta$ è la funzione di transizione

$$ \delta:Q \times \Sigma_\epsilon \times \Gamma \rarr \mathcal P_{\text{fin}}(Q\times \Gamma^*) $$

dove la notazione $\mathcal P_{\text{fin}}(S)$ indica l’insieme dei sottoinsiemi finiti di $S$.

Quello appena definito è un automa non deterministico con $\epsilon$-mosse, un’estensione degli $\epsilon$-NFA: dalla definizione di questi ultimi rimagono invariati gli elementi $Q, \Sigma, q_0$ e $F$.

Lo stack viene modellato come una stringa di simboli di un apposito alfabeto $\Gamma$. Per convenzione, il simbolo più a sinistra della stringa è quello in cima allo stack, cioè una stringa $a_1\dots a_n$, corrispondente al seguente stack:

Quando si definiscono i passi di computazione, sarà comodo trattare solo i casi in cui lo stack non è vuoto, così da avere sempre un simbolo in cima allo stack, in base al quale scegliere la transizione da eseguire. Allora, è necessario che lo stack contenga inizialmente (almeno) un simbolo: a tale scopo, si sceglie un simbolo iniziale di stack $Z_0 \in \Gamma$. Spesso, sarà utile fare in modo che $Z_0$ rimanga sempre e solo in fondo allo stack, e sia distinto da tutti gli altri simboli inseriti nello stack:

in questo modo, quando l’automa troverà $Z_0$ come elemento in cima, saprà di essere arrivato al fondo dello stack.