automa a pila (PDA)

Potenziamo l’automa non deterministico a stati finiti (NFA) in modo da ottenere un automa equivalente alla CFG. Sarà non deterministico, ma avrà in aggiunta una pila, in cui può fare:

• push e pop di simboli in modalità LIFO;
• sovrascrizione del simbolo in cima.

La notazione $a;b\to c$ vuol dire: “se l’input è $a$ e sulla cima della pila c’è $b$, allora fai pop e pusha $c$“.

Definizioni

Definizione formale: un automa a pila (PDA), anche detto pushdown automaton, è una sestupla $(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ dove:

• $Q$ è un insieme finito di stati;
• $\Sigma$ è un insieme finito dei simboli dell’alfabeto che compongono tutti gli input possibili;
• $\Gamma$ è l’alfabeto finito di pila;
• $\delta :Q\times {\Sigma }_{\epsilon }\to {\Gamma }_{\epsilon }\to \mathcal{P}(Q\times {\Gamma }_{\epsilon })$ è la funzione di transizione;
• $q_0$ è lo stato iniziale;
• $F\subseteq Q$ è l’insieme degli stati finali.

Definizione di come computa: Sia $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$. $M$ accetta $w=w_1,\dots ,w_m\in {\Sigma }^{\star }$ se $\exists r_0,\dots ,r_m\in Q$ e stringhe $s_0,\dots ,s_m$:

($S$ è la pila, $a$ è la sua vecchia cima, $b$ è la sua nuova cima)

Se le seguenti condizioni sono vere:

• $r_0=q_0;s_0=\epsilon$
• $\forall i=0\dots m(r_{i+1},b)\in S(r_i,w_{i+1},a)$
• $s_i=at{s}_{i+1}=bt\text{con}a,b\in {\Gamma }_{\epsilon }$

Allora $r_m\in F$, cioè $M$ accetta $r$.

Al posto di definirlo come abbiamo fatto, cioè con gli stati intermedi, si può definirlo più facilmente con le configurazioni.

N.B.: Sarà utile semplificare (senza perdita di generalità) che un PDA svuota sempre la pila prima di accettare: $(q_0,w,\epsilon ){⊢}_M^{\star }(q\in F,\epsilon ,\epsilon )$.

Esempio: PDA per $L=\{0^n{1}^n:n\ge 0\}$.

Idea:

• fino a che leggo ‘0’, push ‘0’.
• quando inizio a leggere ‘1’, pop ‘0’.
• accetto se e solo se ho finito con la pila vuota. Una tecnica comune per poter capire se è vuota è mettere un “simbolo marcatore”, che segna l’inizio ($ nell’esempio).