Automa a pila

Da Wikipedia, l'enciclopedia libera.

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 formale[modifica | modifica wikitesto]

Automa a pila non deterministico[modifica | modifica wikitesto]

L'automa a pila non deterministico è un sistema formale composto da , 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 deterministico[modifica | modifica wikitesto]

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 pila[modifica | modifica wikitesto]

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

Accettazione degli automi a pila[modifica | modifica wikitesto]

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

Accettazione per pila vuota[modifica | modifica wikitesto]

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 finale[modifica | modifica wikitesto]

PDA per (per stato finale)

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.

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