Automi a pila

Un automa a pila (o PDA) è una sestupla $(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ equivalente alle CFG che sfrutta uno stack:

e i suoi componenti sono definiti come:

1. $Q$ è l'insieme degli stati
2. $\Sigma$ è l'alfabeto dell'input
3. $\Gamma$ è l'alfabeto dello stack
4. $\delta :Q\times {\Sigma }_{ϵ}\times {\Gamma }_{ϵ}\to P(Q\times {\Gamma }_{ϵ})$ è la funzione di transizione, con ${\Sigma }_{ϵ}=\Sigma \cup \{ϵ\}$ e ${\Gamma }_{ϵ}=\Gamma \cup \{ϵ\}$
5. $q_0\in Q$ è lo stato iniziale
6. $F\subseteq Q$ è l'insieme degli stati finali

Un PDA accetta $w=w_1{w}_2\cdots w_m:w_i\in {\Sigma }_{ϵ}$ se esistono $r_0,r_1,...,r_m\in Q$ e $s_0,s_1,...,s_m\in {\Gamma }^{\ast }$ per cui:

• $r_0=q_0$ e $s_0=ϵ$: $M$ comincia dallo stato iniziale e con la pila $s_0$ vuota
• $r_m\in F$: alla fine dell'input, $M$ è su uno stato accettante
• $(r_{i+1},b)\in \delta (r_i,w_{i+1},a),\forall i=0,...,m-1$, con $s_i=at,s_{i+1}=bt$ per $a,b\in {\Gamma }_{ϵ}$ e $t\in {\Gamma }^{\ast }$: il prossimo stato $r_{i+1}$ e pila $s_{i+1}$ sono determinati dallo stato $r_i$, l'input $w_{i+1}$ e la cima $a$ della pila $s_i$

Per esempio, l'automa che riconosce $\left\{0^n{1}^n|n\ge 0\right\}$

sarà rappresentato da $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$, dove: $$\begin{array}{rl}Q& =\{q_1,q_2,q_3,q_4\}\\ \Sigma & =\{0,1\}\\ \Gamma & =\{0,\$\}\\ q_0& =q_1\\ F& =\{q_1,q_4\}\end{array}\wedge \{\begin{array}{l}\delta (q_1,ϵ,ϵ)=\{(q_2,\$)\}\\ \delta (q_2,0,ϵ)=\{(q_2,0)\}\\ \delta (q_2,1,0)=\{(q_3,ϵ)\}\\ \delta (q_3,1,0)=\{(q_3,ϵ)\}\\ \delta (q_3,ϵ,\$)=\{(q_4,ϵ)\}\end{array}$$

Un altro esempio è l'automa che riconosce $\left\{a^i{b}^j{c}^k|i,j,k\ge 0\wedge i=j\vee i=k\right\}$:

Equivalenza

Si può dimostrare che un linguaggio $A$ è context-free sse esiste un PDA $P$ tale che $L(P)=A$, infatti:

1. Condizione sufficiente ($\Rightarrow$)

   Dato che $A$ è context-free esiste una CFG $G$ che lo riconosce. Basterà quindi trasformare la CFG in PDA:

   1. Inserire sullo stack prima $\$$ e poi $S$, ovvero lo start symbol
   2. Per ogni regola $A\to w$, alla lettura di $A$ sullo stack rimuovere $A$ e inserirci $w$
   3. Per ogni terminale $a$, alla lettura di $a$ sullo stack rimuovere $a$ mentre viene anche letto sull'input

   Per esempio, la CFG $$\begin{array}{rl}& S\to aTb\mid b\\ & T\to Ta\mid ϵ\end{array}$$ si potrà convertire nel seguente PDA:

   

2. Condizione necessaria ($\Leftarrow$)

   Per dimostrarlo si vuole semplificare $P$ in modo che:

   • Abbia un unico stato accettante $q_a$: con $ϵ$-transizioni dagli stati finali a $q_a$
   • Svuoti lo stack prima di accettare: con $ϵ,a\to ϵ,\forall a\in \Gamma$ sullo stato finale
   • Inserisca o rimuova un simbolo sullo stack ad ogni transizione: sostituendo le transizioni $a,b\to c$ con $a,b\to ϵ$ e $ϵ,ϵ\to c$, e le transizioni $a,ϵ\to ϵ$ con $a,ϵ\to b$ e $ϵ,b\to ϵ$

   Sia quindi $P=(Q,\Sigma ,\Gamma ,\delta ,q_0,\{q_a\})$, $\left\{A_{pq}|p,q\in Q\right\}$ i non-terminali e $A_{q_0,q_a}$ lo start symbol di $G$:

   1. Per ogni $p,q,r,s\in Q$, $u\in \Gamma$ e $a,b\in {\Sigma }_{ϵ}$ se $\delta (p,a,ϵ)$ contiene $(r,u)$ e $\delta (s,b,u)$ contiene $(q,ϵ)$, allora a $G$ viene aggiunta la regola $A_{pq}\to a{A}_{rs}b$
   2. Per ogni $p,q,r\in Q$ viene aggiunta la regola $A_{pq}\to A_{pr}{A}_{rq}$ a $G$
   3. Per ogni $p\in Q$ viene aggiunta la regola $A_{pp}\to ϵ$ a $G$

   Il primo punto è il caso in cui per andare da $p$ a $q$ il primo simbolo aggiunto e l'ultimo rimosso dallo stack è lo stesso, mentre il secondo è il caso in cui il simbolo viene rimosso prima di arrivare a $q$.

   Si può quindi dimostrare che $A_{pq}{\Rightarrow }^{\ast }x$ sse $x$ porta $P$ da $p$ con lo stack vuoto a $q$ con lo stack vuoto:

   1. Condizione sufficiente ($\Rightarrow$), per induzione sul numero di passi di derivazione:

      • Caso base con $1$ passo, ovvero senza non-terminali: usa $A_{pp}\to ϵ$ che non tocca lo stack

      • Passo induttivo con $k+1$ passi, assumendo che valga fino a $k\ge 1$:

        Il primo passo può essere $A_{pq}\Rightarrow a{A}_{rs}b$ oppure $A_{pq}\Rightarrow A_{pr}{A}_{rq}$.

        Nel primo caso, con $x=ayb$, si ha che $A_{rs}{\Rightarrow }^{\ast }y$ in $k$ passi, quindi per ipotesi induttiva parte da $r$ e arriva a $s$ con lo stack uguale. Essendo una regola di $G$, da $p$ a $r$ aggiunge $u$ sullo stack e da $s$ a $q$ lo rimuove, verificando la proprietà.

        Nel secondo caso, con $x=yz$, si ha che $A_{pr}{\Rightarrow }^{\ast }y$ e $A_{rq}{\Rightarrow }^{\ast }z$, entrambe fino a $k$ passi. Per ipotesi induttiva lo stack ritorna vuoto da $p$ a $r$ e da $r$ a $q$, verificando la proprietà.

   2. Condizione necessaria ($\Leftarrow$), per induzione sul numero di passi della computazione di $P$ da $p$ a $q$:

      • Caso base con $0$ passi: va da un $p$ a $p$ senza leggere nulla, quindi $x=ϵ$ e infatti $A_{pp}\Rightarrow ϵ$

      • Passo induttivo con $k+1$ passi, assumendo che valga fino a $k\ge 1$:

        I $k+1$ passi per $x$ da $p$ a $q$ hanno lo stack vuoto all'inizio e alla fine oppure anche altrove.

        Nel primo caso, lo stesso simbolo $u$ va inserito leggendo $a$ da $p$ ad uno stato $r$ e rimosso leggendo $b$ da uno stato $s$ a $q$, quindi $A_{pq}\Rightarrow a{A}_{rs}b$. Ci sono $k-1$ passi da $r$ a $s$ quindi, dato $x=ayb$, per ipotesi induttiva $A_{rs}{\Rightarrow }^{\ast }y$ e allora $A_{pq}{\Rightarrow }^{\ast }ayb=x$.

        Nel secondo caso lo stack si svuota anche su $r$ quindi da $p$ a $r$ e da $r$ a $q$ sono al più $k$ passi, per cui, dato $x=yz$, per ipotesi induttiva $A_{pr}{\Rightarrow }^{\ast }y$ e $A_{rq}{\Rightarrow }^{\ast }z$ e allora $A_{pq}{\Rightarrow }^{\ast }yz=x$.