Automa a pila

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.

Definizione Formale

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.

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

Configurazione di un automa a pila

Dato un automa a pila M = (Σ, Γ, Zø, Q, qø, F, δ) si dice configurazione di M una tripla , dove q appartiene a Q, x a Σ* e γ a Γ*.

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=γ=ε. In base a tale definizione un linguaggio è accettato da un automa a pila se al termine dell'elaborazione di una stringa la pila è vuota.

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.

Teorie dell'informatica | Linguaggi formali