Automa a pila
Da Wikipedia, l'enciclopedia libera.
Un automa a pila o automa push-down è una macchina astratta adatta a riconoscere ed accettare quei linguaggi che nelle grammatiche formali sono detti di tipo 2, non contestuali o context-free. Il nome di tale macchina deriva dal fatto che come memoria di lavoro utilizza una struttura dati detta stack.
Indice |
[modifica] Definizione Formale
[modifica] Automa a pila non deterministico
L'automa a pila non deterministico è un sistema formale composto da M=(Σ, Γ, Zø, Q, qø, F, δ), dove:
- Σ è l'alfabeto di input;
- Γ è l'alfabeto dei simboli della pila;
- Zø è il carattere (appartenente a Γ) iniziale della pila;
- Q è un insieme finito e non vuoto di stati;
- qø (appartenente a Q) è lo stato iniziale;
- F è un sottoinsieme di Q contenente gli stati finali;
- δ: Q × (Σ U {ε}) × Γ → P(Q × Γ*) è la funzione parziale di transizione;
- ε è la stringa vuota.
[modifica] 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 Ζ di Γ e per ogni stato q di Q:
|δ(q, a, Z)| + |δ(q, e, Z)| < 2
[modifica] 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 Σ* e γ a Γ*.
[modifica] Accettazione degli automi a pila
Un automa a pila ha due diversi modi di accettare un linguaggio:
[modifica] Accettazione per pila vuota
Dato un automa a pila M, una sua configurazione è di accettazione se x=γ=ε. In base a tale definizione un linguaggio è accettato da un automa a pila se al termine dell'elaborazione di una stringa la pila è vuota.
[modifica] Accettazione per stato finale
Dato un automa a pila M, una sua configurazione (q, x, γ) è di accettazione se x=ε e q appartiene a F. Secondo questa definizione una stringa x è accettata da M se e solo se al termine dell'elaborazione l'automa si trova in uno stato finale.
Ė importante notare che un automa a pila costruito per accettare un dato linguaggio è in grado di farlo solo in uno dei due modi sopra descritti: si potranno avere automi che riconoscono un dato linguaggio L per pila vuota o per stato finale, ma non uno che lo riconosca per pila vuota e per stato finale.
| Teoria degli automi: linguaggi formali e grammatiche formali | |||
|---|---|---|---|
| gerarchia di Chomsky |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Context-free | Context-free | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
