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.
Vediamo ora l'esempio di un automa a pila non 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 inizialmente 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.