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 = (Σ,Γ,Z₀,Q,q₀,F,δ), dove:

1. Σ è l'alfabeto di input;
2. Γ è l'alfabeto dei simboli della pila;
3. Z₀ è il carattere (appartenente a Γ) iniziale della pila;
4. Q è un insieme finito e non vuoto di stati;
5. q₀ (appartenente a Q) è lo stato iniziale;
6. F è un sottoinsieme di Q contenente gli stati finali;
7. $\delta: Q \times (\Sigma \cup {\epsilon}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^\star)$ è la funzione parziale di transizione (P(A) indica le parti finite dell'insieme A);
8. $\epsilon$ è la stringa vuota.

Automa a pila deterministico

Un automa a pila deterministico è un automa a pila M = (Σ,Γ,Z₀,Q,q₀,F,δ) tale che per ogni carattere a di Σ, per ogni stato Z di Γ 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 = (Σ,Γ,Z₀,Q,q₀,F,δ) si dice configurazione di M una tripla (q,x,γ), dove q appartiene a Q, x a $\Sigma^\star$ e γ 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=\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,γ) è 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₁ se e solo se L è un linguaggio accettato per stato finale da un automa a pila M₂. 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