Automa a pila

Un automa a pila o Push Down Automa (PDA) è una macchina astratta adatta a riconoscere ed accettare quei linguaggi che nelle grammatiche formali sono detti liberi da contesto (o di tipo 2, o non contestuali, o context-free). Il nome di tale macchina deriva dal fatto che come memoria di lavoro utilizza una struttura dati detta stack.

Definizione Formale

Automa a pila non deterministico

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

1. $\Sigma$ è l'alfabeto di input;
2. $\Gamma$ è l'alfabeto dei simboli della pila;
3. $Z_0 \in \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 (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}_{finite}(Q \times \Gamma^\star)$ è la funzione parziale di transizione ($\varepsilon$ è la stringa vuota).

Automa a pila deterministico

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

Configurazione di un automa a pila

Dato un automa a pila $M = (\Sigma, \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 $\Sigma^\star$ e $\gamma$ a $\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=\varepsilon$. 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=\varepsilon$ 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.

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica	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 del proprio sovrainsieme di categoria direttamente sottostante.

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica