equivalenza tra PDA e CFG

Teorema: Un linguaggio è acontestuale se e solo se esiste un automa a pila (PDA) che lo riconosce.

Dimostrazione $⟹$

Se $L=L(G)$ per una qualche CFG $G$, allora esiste un PDA $P$ tale che $L(P)=L$

Intuizione: Dato un input $w\in {\Sigma }^{\star }$ $P$ userà la pila e il non determinismo per cercare di capire se $w$ è generabile da $G$.

Ad esempio:

$$\begin{gathered} S\to V_1\mid V_2 \\ {V}_1\to b{V}_2{V}_3 \\ {V}_1\to c{V}_2{V}_4 \\ {V}_2\to c \\ {V}_4\to d \end{gathered}$$

La pila contiene le sostituzioni. Il determinismo serve perché l’automa deve esplorare per forza tutti gli alberi di sostituzione.

All’inizio nella pila (leggi da sinistra a destra) ci sarà \mid \\ S \mid$.Laprimasostituzionesar\grave{a}$\mid $\ V_{2}\ a\ V_{1} \mid$.

Di fatto $P$ esplora in profondità tutti gli alberi generabili da $G$.

In dettaglio:

• Inserisce \\ S$ nella pila
• e ripete:
  • Se il cima alla pila c’è $A\in V$, sceglile non deterministicamente le regole del tipo $A\to \dots$ di $G$ e sostituisce $A$.
  • Se nella pila c’è $a\in \Sigma$, faccio pop di $a$ e provo a fare match con il prossimo carattere di input.

(nel disegno più passi sono stati eseguiti in uno per semplicità.)

Formalmente, $P=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$.

Per semplicità, ammettiamo senza perdita di generalità:

3 stati = $\{q_{\text{st}},q_{\text{acc}},q_{\text{loop}}\}$ = $Q$.

All’inizio inserisce \\ S$:$\delta(q_{\text{start}}, \varepsilon, \varepsilon) = {(q_{\text{loop}}, S\ $)}$ Poi:

• Se la cima contiene la variabile $A$: $\delta (q_{\text{loop}},\epsilon ,a)=\{(q_{\text{loop}},w):A\to w\in G\}$
• Se la cima contiene il terminale $a$: $\delta (q_{\text{loop}},a,a)=\{(q_{\text{loop}},\epsilon )\}$
• Se la cima contiene \$$: \delta(q_{\text{loop}}, \varepsilon, $) = {(q_{\text{acc}}, \varepsilon)}$

Dimostrazione $⟸$

Se $L=L(P)$ per una qualche PDA $P$, allora esiste un CFG $G$ tale che $L(G)=L$

Dato un PDA $P$, facciamo la grammatica equivalente $G$.

$$P=(Q,\Sigma ,\Gamma ,\delta ,q_0,\{q_{\text{acc}}\})$$ $$G=(\Sigma ,V,R,S)$$

Per ogni coppia di stati $p,q$ pongo $V=\{A_{pq}:p,q\in Q\}$ e $S=A{q}_0{q}_{\text{acc}}$.

Per semplificare la $G$ assumo che $G$ è in forma normale di Chomsky e $P$ è in forma canonica:

• Prima di accettare svuota la pila.
• Non fa mai push e pop insieme, ma separatamente.

Le regole: todo

1. Per ogni $p,q,V\in \Gamma ,S\in Q$ e $a,b\in \Sigma A_{PQ}\to a{A}_{RS}b$.