title: Automa a pila
text: # 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 $M=(\Sigma ,\Gamma ,Z_{0},Q,q_{0},F,\delta )$, dove:
  
  * $\Sigma$ è l'alfabeto di input;
  * $\Gamma$ è l'alfabeto dei simboli della pila;
  * $Z_{0}\in \Gamma$ è il carattere iniziale della pila;
  * $Q$ è un insieme finito e non vuoto di stati;
  * $q_{0}\in Q$ è lo stato iniziale;
  * $F\subseteq Q$ è l'insieme degli stati finali;
  * $\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
  
  $\{0^{n}1^{n}\mid n\geq 0\}$
  
  $M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$, con
  
  * alfabeto di input: $\Sigma =\{0,1\}$
  * alfabeto dei simboli della pila: $\Gamma =\{A,Z\}$
  * carattere iniziale della pila: $Z\in \Gamma$
  * stati: $Q=\{p,q,r\}$
  * stato iniziale: $q_{0}=p$
  * stati finali: $F=\{r\}$
  * funzione di transizione ($\varepsilon$ è la stringa vuota) – costituita dalle seguenti 6 istruzioni:
  
         $(p,0,Z,p,AZ)$,
         $(p,0,A,p,AA)$,
         $(p,\epsilon ,Z,q,Z)$,
         $(p,\epsilon ,A,q,A)$,
         $(q,1,A,q,\epsilon )$,
         $(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.
  
  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.
  
  