Lemma 2.21

Se un linguaggio è context-free, allora esiste un automa a pila che lo riconosce.

---

IDEA. $\quad$ Sia $\Large A$ un $\Large CFL$. Dalla definizione sappiamo che esiste una, $\Large CFG,\ G$, che genera $\Large A$. Mostriamo come trasformare $\Large G$ in un $\Large PDA$ equivalente che chiamiamo $\Large P$.

Il $\Large PDA\ P$ che ora descriviamo, opererà accettando il suo input $\Large w$, se $\Large G$ genera tale input, determinando se esiste una derivazione per $\Large w$.

Ricordiamo che una derivazione è semplicemente la sequenza di sostituzioni fatte nel processo di generazione di una stringa mediante una grammatica.

Ogni passo di una derivazione produce una stringa intermedia di variabili e terminali.

Noi progettiamo $\Large P$ in modo che possa stabilire se una serie di sostituzioni che usano le regole di $\Large G$ possa condurre dalla variabile iniziale a $\Large w$.

Una delle difficoltà nell'esaminare se esiste una derivazione per $\Large w$ consiste nel capire quali sostituzioni fare.

Il non determinismo di un $\Large PDA$ gli consente di ipotizzare la sequenza di sostituzioni giuste.

In ogni passo della derivazione, una delle regole per una particolare variabile è scelta non deterministicamente e usata per sostituire quella variabile.

Il $\Large PDA\ P$ inizia scrivendo la variabile iniziale sulla sua pila. Esso passa attraverso una serie di stringhe intermedie, facendo una sostituzione dietro l'altra.

Infine può giungere a una stringa che contiene solo simboli terminali, il che significa che ha usato la grammatica per derivare una stringa.

Allora $\Large P$ accetta se questa stringa è identica alla stringa che ha ricevuto in input. Implementare questa strategia su un $\Large PDA$ richiede un'idea supplementare.

Dobbiamo capire come il $\Large PDA$ immagazzina le stringhe intermedie quando passa dall'una all'altra.

Usare semplicemente la pila per immagazzinare ciascuna stringa intermedia è allettante.

Tuttavia non funziona del tutto poiché il $\Large PDA$ ha bisogno dì trovare le variabili nelle stringhe intermedie e fare sostituzioni.

Il $\Large PDA$ può accedere solo al simbolo sulla cima della pila e questo potrebbe essere un simbolo terminale e non una variabile.

Il modo per aggirare questo problema è mantenere solo parte della stringa intermedia sulla pila: i simboli che iniziano con la prima variabile nella stringa intermedia.

Tutti i simboli terminali che compaiono prima della prima variabile sono subito abbinati con i simboli nella stringa di input.

Quello che segue è una descrizione informale di $\Large P$.

1. Inserisce il simbolo marcatore $ e la variabile iniziale sulla pila.

2. Ripete i seguenti passi.

$\quad \quad$ a. Se sulla cima della pila c'è il simbolo di una variabile $\Large A$, sceglie non deterministicamente una delle regole per $\Large A$ e sostituisce $\Large A$ con la stringa sul lato destro della $\quad \quad \quad$ regola.

$\quad \quad$ b. Se sulla cima della pila c'è un simbolo terminale $\Large a$, legge il simbolo seguente dall'input e lo confronta con $\Large a$.

$\quad \quad \quad$ Se essi sono uguali, ripete. Se essi non sono uguali, rifiuta su questo ramo del non determinismo.

$\quad \quad$ c. Se sulla cima della pila c'è il simbolo $, entra nello stato accettante. In questo modo accetta l'input se esso è stato completamente letto.

---

DIMOSTRAZIONE Ora diamo i dettagli formali della costruzione dell'automa a pila $\Large P = (Q,\ \Sigma,\ \Gamma,\ q_{start},\ F)$.

Per rendere più chiara la costruzione, usiamo una notazione abbreviata per la funzione di transizione.

Questa notazione fornisce un modo per scrivere un'intera stringa sulla pila in un passo della macchina.

Possiamo simulare quest'azione introducendo stati aggiuntivi per scrivere la stringa un simbolo alla volta, come realizzato nella seguente costruzione formale.

Siano $\Large q$ ed $\Large r$ stati del $\Large PDA$ e siano $\Large a$ in $\Large \Sigma_{\epsilon}$ ed $\Large s$ in $\Large \Gamma_{\epsilon}$. Supponiamo di volere che il $\Large PDA$ vada da $\Large q$ a $\Large r$ quando legge $\Large a$ ed elimina $\Large s$.

Inoltre, vogliamo che esso inserisca l'intera stringa $\Large u = u_1 \dots u_l$ sulla pila simultaneamente.

Possiamo eseguire questa azione introducendo nuovi stati $\Large q_1, \dots , q_{l-1}$ e definendo la funzione di transizione come segue:

$$ \Large \delta(q,\ a,\ s)\ \text{contiene}\ (q_1,\ u_l), $$

$$ \Large \delta(q_1,\ \epsilon,\ \epsilon) = \{(q_2, u_{l-1})\}, $$

$$ \Large \delta(q_2,\ \epsilon,\ \epsilon) = \{(q_3, u_{l-2})\}, $$

$$ \large \vdots $$

$$ \Large \delta(q_{l-1},\ \epsilon,\ \epsilon) = \{(r, u_1)\}. $$

Useremo la notazione $\Large (r,\ u) \in \delta(q,\ a,\ s)$ per denotare che quando $\Large q$ è lo stato in cui si trova l'automa, $\Large a$ è il prossimo simbolo di input ed $\Large s$ è il simbolo sulla cima della pila, il $\Large PDA$ può leggere $\Large a$ ed eliminare $\Large s$, poi inserire la stringa $\Large u$ nella pila e passare nello stato $\Large r$.

Gli stati di $\Large P$ sono $\Large Q = \{q_{start},\ q_{loop},\ q_{accept}\} \cup E$, dove $\Large E$ è l'insieme degli stati necessari per realizzare l'abbreviazione appena descritta.

Lo stato iniziale è $\Large q_{start}$. L'unico stato accettante è $\Large q_{accept}$. La funzione di transizione è definita come segue.

Cominciamo inizializzando la pila inserendo i simboli $ and $\Large S$, realizzando cosi il passo 1 nella descrizione informale:

$$ \Large \delta(q_{start},\ \epsilon,\ \epsilon) = \{(q_{loop},\ S\$)\}. $$

Poi aggiungiamo le transizioni per il ciclo principale del passo 2. In primo luogo, trattiamo il caso (a) in cui la cima della pila contiene una variabile. Poniamo

$$ \Large \delta(q_{loop},\ \epsilon,\ A) = \{(q_{loop},\ w) | \text{dove}\ A \rightarrow w\ \text{è una regola in}\ R\}. $$

In secondo luogo, trattiamo il caso (b) in cui la cima della pila contiene un terminale. Poniamo $\Large \delta(q_{loop},\ a,\ a) = \{(q_{loop},\ \epsilon)\}$.

Infine: trattiamo il caso (c) in cui il marcatore scelto per indicare la pila vuota $ è sulla cima della pila. Poniamo $\Large \delta(q_{loop},\ \epsilon,\ \$) = \{(q_{accept},\ \epsilon)\}$.

Questo completa la prova del Lemma 2.21.