Automa a pila

Template:F 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.

Definizione formale

Automa a pila non deterministico

L'automa a pila non deterministico è un sistema formale composto da $M=(\mathrm{\Sigma },\mathrm{\Gamma },Z_0,Q,q_0,F,\delta )$, dove:

1. $\mathrm{\Sigma }$ è l'alfabeto di input;
2. $\mathrm{\Gamma }$ è l'alfabeto dei simboli della pila;
3. $Z_0\in \mathrm{\Gamma }$ è il carattere iniziale della pila;
4. $Q$ è un insieme finito e non vuoto di stati;
5. $q_0\in Q$ è lo stato iniziale;
6. $F\subseteq Q$ è l'insieme degli stati finali;
7. $\delta :Q\times (\mathrm{\Sigma }\cup \{\epsilon \})\times \mathrm{\Gamma }\to {𝒫}_{finite}(Q\times {\mathrm{\Gamma }}^{\star })$ è la funzione parziale di transizione ($\epsilon$ è la stringa vuota).

Automa a pila deterministico

Un automa a pila deterministico è un automa a pila $M=(\mathrm{\Sigma },\mathrm{\Gamma },Z_0,Q,q_0,F,\delta )$ tale che per ogni carattere a di $\mathrm{\Sigma }$, per ogni stato $Z$ di $\mathrm{\Gamma }$ e per ogni stato $q$ di $Q$ si ha $|\delta (q,a,Z)|+|\delta (q,\epsilon ,Z)|<2$

Configurazione di un automa a pila

Dato un automa a pila $M=(\mathrm{\Sigma },\mathrm{\Gamma },Z_0,Q,q_0,F,\delta )$ si dice configurazione di $M$ una tripla $(q,x,\gamma )$, dove $q$ appartiene a $Q$, $x$ a ${\mathrm{\Sigma }}^{\star }$ e $\gamma$ a ${\mathrm{\Gamma }}^{\star }$.

Accettazione degli automi a pila

Un automa a pila ha due diversi modi di accettare un linguaggio:

Accettazione per pila vuota

Dato un automa a pila $M$, una sua configurazione è di accettazione se $x=\gamma =\epsilon$. In base a tale definizione una stringa $x$ è accettata da un automa a pila se e solo se al termine dell'elaborazione di $x$ la pila è vuota.

Accettazione per stato finale

Dato un automa a pila $M$, una sua configurazione $(q,x,\gamma )$ è di accettazione se $x=\epsilon$ e $q$ appartiene a $F$. Secondo questa definizione una stringa $x$ è accettata da $M$ se e solo se al termine dell'elaborazione di $x$ stringa l'automa si trova in uno stato finale.

In generale, dato un automa a pila $M$, il linguaggio riconosciuto da $M$ per pila vuota è diverso dal linguaggio riconosciuto da $M$ per stato finale. È importante notare, tuttavia, che la classe dei linguaggi riconosciuti dagli automi a pila non cambia sia che si scelga l'accettazione per pila vuota che per stato finale. Vale, cioè che $L$ è un linguaggio accettato per pila vuota da un automa a pila $M_1$ se e solo se $L$ è un linguaggio accettato per stato finale da un automa a pila $M_2$. In particolare, la classe dei linguaggi accettati dagli automi a pila coincide con quella dei linguaggi liberi da contesto.