Automa a pila

Un automa a pila o Push Down Automa (PDA) è 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 formaleModifica

Automa a pila non deterministicoModifica

L'automa a pila non deterministico è un sistema formale composto da  [1], dove:

  1.   è l'alfabeto di input;
  2.   è l'alfabeto dei simboli della pila;
  3.   è il carattere iniziale della pila;
  4.   è un insieme finito e non vuoto di stati;
  5.   è lo stato iniziale;
  6.   è l'insieme degli stati finali;
  7.   è la funzione parziale di transizione (  è la stringa vuota).

Automa a pila deterministicoModifica

Un automa a pila deterministico è un automa a pila   tale che per ogni carattere a di  , per ogni stato   di   e per ogni stato   di   si ha  

Configurazione di un automa a pilaModifica

Dato un automa a pila   si dice configurazione di   una tripla  , dove   appartiene a  ,   a   e   a  .

Accettazione degli automi a pilaModifica

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

Accettazione per pila vuotaModifica

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

Accettazione per stato finaleModifica

Esempio

Vediamo ora l'esempio di un automa a pila deterministico che riconosca il linguaggio   per stato finale:

 
PDA per   (per stato finale)

 , con

  • alfabeto di input:  
  • alfabeto dei simboli della pila:  
  • carattere iniziale della pila:  
  • stati:  
  • stato iniziale:  
  • stati finali:  
  • funzione di transizione (  è la stringa vuota) – costituita dalle seguenti 6 istruzioni:
 ,
 ,
 ,
 ,
 ,
 .

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 inizilamente 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  , una sua configurazione   è di accettazione se   e   appartiene a  . Secondo questa definizione una stringa   è accettata da   se e solo se al termine dell'elaborazione di   stringa l'automa si trova in uno stato finale.

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

NoteModifica

  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 progettiModifica

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.
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica