Automa a pila

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

Automa a pila non deterministico[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

Accettazione per pila vuota[modifica | modifica sorgente]

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[modifica | modifica sorgente]

PDA per \{0^n1^n \mid n \ge 0\} (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 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 sottostante.
informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica