Parliamo ora dei linguaggi che possono essere generati da grammatiche libere da contesto.
Def.: Un linguaggio $L$ è libero da contesto $\iff$ esiste una grammatica libera da contesto $G$ con $L=\mathcal{L}[G]$
Def.: Una forma sentenziale di una grammatica $G$ è una stringa $\alpha\in(T\cup NT)^$ tale che $S\implies^\alpha$, dove $S$ è il simbolo iniziale di $G$. Una forma sentenziale è una sentenza di $G$ $\iff$è composta da soli terminali.
Def.: Il linguaggio generato da una grammatica è l'insieme delle sue sentenze.
Prendiamo il linguaggio libero non regolare $\{a^nb^n|n\geq0\}$; per riconoscere questo linguaggio non basta un automa finito in quanto bisognerebbe prima contare e memorizzare il numero di $a$ e poi verificare se corrisponde al numero di $b$. Per fare una simile operazione bisogna utilizzare automi dotati di un metodo di memorizzazione.
Qui entra in gioco l'automa a pila, che ha a disposizione uno stack dove poter memorizzare un numero arbitrario di simboli (con la solita politica LIFO degli stack).
In questo tipo di automa una transizione non dipende solo dal simbolo di input e dallo stato, ma anche dal simbolo memorizzato in cima allo stack.
Inoltre nel passaggio da uno stato all'altro l'automa può, oltre al passaggio in sé, anche depositare simboli sullo stack.
Def.: Un automa a pila non deterministico (o PDA, push-down automaton) è una 7-upla $(\Sigma,Q,\Gamma,\delta,q_0,\bot,F)$, dove:
- $\Sigma$ è un alfabeto finito (i simboli di input);
- $Q$ è un insieme finito (gli stati);
- $\Gamma$ è un insieme finito (i simboli della pila);
- $\delta$ è la funzione di transizione con tipo $\delta:Q\times(\Sigma\cup\{\epsilon\})\times\Gamma\rarr \mathcal{P}_{fin}(Q\times\Gamma^*)$;
- $q_0\in Q$ è lo stato iniziale;
- $\bot\in\Gamma$ è il simbolo di fondo pila;
- $F\sube Q$ sono gli stati finali.
Per avere l'immagine di un PDA in un dato momento non basta più sapere solo lo stato in cui si trova l'automa e l'input attuale, serve sapere anche l'elemento in cima alla pila in quel momento.
Una configurazione di un PDA è una tripla $(q,w,\beta)$ con $q\in Q$ (lo stato in cui si trova il PDA), $w\in\Sigma^$ (l'input ancora non letto) e $\beta\in\Gamma^$ (la stringa sulla pila).
Possiamo quindi descrivere una mossa come un passaggio fra due configurazioni.
Un PDA accetta il proprio input se l'automa consuma tutto l'input e si trova in uno stato finale, indipendentemente da cosa sia rimasto sulla pila. Oppure possiamo accettare un input nel momento in cui la pila sia stata svuotata (togliendo anche il simbolo di fondo fila).
Teorema: Un linguaggio L è libero da contesto $\iff$è accettato da un PDA.
È possibile eliminare il non determinismo da un PDA?
Capiamo prima quando un PDA è deterministico: