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.

Definizione formale

Automa a pila non deterministico

L'automa a pila non deterministico è un sistema formale composto da ${\displaystyle M=(\Sigma ,\Gamma ,Z_{0},Q,q_{0},F,\delta )}$[1], dove:

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

Automa a pila deterministico

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

Configurazione di un automa a pila

Dato un automa a pila ${\displaystyle M=(\Sigma ,\Gamma ,Z_{0},Q,q_{0},F,\delta )}$ si dice configurazione di ${\displaystyle M}$ una tripla ${\displaystyle (q,x,\gamma )}$, dove ${\displaystyle q}$ appartiene a ${\displaystyle Q}$, ${\displaystyle x}$ a ${\displaystyle \Sigma ^{\star }}$ e ${\displaystyle \gamma }$ a ${\displaystyle \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 ${\displaystyle M}$, una sua configurazione è di accettazione se ${\displaystyle x=\gamma =\varepsilon }$. In base a tale definizione una stringa ${\displaystyle x}$ è accettata da un automa a pila se e solo se al termine dell'elaborazione di ${\displaystyle x}$ la pila è vuota.

Accettazione per stato finale

Esempio

Vediamo ora l'esempio di un automa a pila non deterministico che riconosca il linguaggio ${\displaystyle \{0^{n}1^{n}\mid n\geq 0\}}$ per stato finale:

PDA per ${\displaystyle \{0^{n}1^{n}\mid n\geq 0\}}$ (per stato finale)

${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)}$, con

• alfabeto di input: ${\displaystyle \Sigma =\{0,1\}}$
• alfabeto dei simboli della pila: ${\displaystyle \Gamma =\{A,Z\}}$
• carattere iniziale della pila: ${\displaystyle Z\in \Gamma }$
• stati: ${\displaystyle Q=\{p,q,r\}}$
• stato iniziale: ${\displaystyle q_{0}=p}$
• stati finali: ${\displaystyle F=\{r\}}$
• funzione di transizione (${\displaystyle \varepsilon }$ è la stringa vuota) – costituita dalle seguenti 6 istruzioni:

${\displaystyle (p,0,Z,p,AZ)}$,

${\displaystyle (p,0,A,p,AA)}$,

${\displaystyle (p,\epsilon ,Z,q,Z)}$,

${\displaystyle (p,\epsilon ,A,q,A)}$,

${\displaystyle (q,1,A,q,\epsilon )}$,

${\displaystyle (q,\epsilon ,Z,r,Z)}$.

Le prime due istruzioni dicono che in uno stato p, per ogni 0 letto viene aggiungo A sulla pila. Aggiungere un A su un altro A è formalizzato dalla scritta AA (così come AZ simbolizza immettere un A su una Z). La terza e quarta istruzione indicano una epsilon-transizione (ossia una transizione non deterministica, che può avvenire in qualsiasi momento) dallo stato p allo stato q. La quinta istruzione dice che in uno stato q, per ogni 1 letto, viene tirato via un A dalla cima della pila. Infine, la sesta istruzione dice che la macchina passa dallo stato q allo stato finale r solamente quando la pila è costituita dalla sola variabile Z (ossia la variabile inizialmente sulla pila). Questo vuol dire che l'automa accetta unicamente la parole dove il numero di 0 sono bilanciate con il numero dei successivi 1.

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

In generale, dato un automa a pila ${\displaystyle M}$, il linguaggio riconosciuto da ${\displaystyle M}$ per pila vuota è diverso dal linguaggio riconosciuto da ${\displaystyle 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 ${\displaystyle L}$ è un linguaggio accettato per pila vuota da un automa a pila ${\displaystyle M_{1}}$ se e solo se ${\displaystyle L}$ è un linguaggio accettato per stato finale da un automa a pila ${\displaystyle M_{2}}$. In particolare, la classe dei linguaggi accettati dagli automi a pila coincide con quella dei linguaggi liberi da contesto.

Note

1. (EN) Dexter C. Kozen, Pushdown Automata, Springer Berlin Heidelberg, 1977, pp. 157–163, DOI:10.1007/978-3-642-85706-5_27, ISBN 978-3-642-85708-9. URL consultato il 3 novembre 2020.

Altri progetti

Altri progetti

• Wikiversità
• Wikimedia Commons

• Wikiversità contiene risorse su Automa a pila
• Wikimedia Commons contiene immagini o altri file su Automa a pila

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica formale	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sovrastante.