5. Linguaggi non context-free e linguaggi context-free deterministici

Nel precedente articolo abbiamo parlato dei linguaggi context-free riconosciuti dalle relative grammatiche e dagli automi a pila. Come fatto in precedenza ora trattiamo i linguaggi non context-free e dei linguaggi contex-free deterministici. Per verificare se un linguaggio è o non è context-free ci si avvale del teorema del pumping lemma per i linguaggi context-free. Questo teorema si basa sulla lunghezza del pumping definito come particolare valore tale che tutt le stringhe più lunghe presenti nel linguaggio possono essere iterate. Diamo una definizione formale del teorema.

Teorema del pumping lemma per i linguaggi context-free

Se A è un linguaggio context-free, allora esiste un numero p. definito lunghezza del pumping, tale che se s è una qualsiasi stringa in A di lunghezza almeno p, allora s può essere divisa in cinque parti s=uvwxyz che soddisfano le seguenti condizioni:

• per ogni $i \geq 0$, $uv^ixy^iz \in A$
• | $vy > 0$ |
• | vxy | $\leq$ p

Quando s è divisa in uvwxyz, nella seconda affermazione viene affermato che v o y non possono essere la stringa vuota, mentre la terza condizione afferma invece che le parti v, x e y insieme hanno lunghezza al più p. Per dimostrare questo teorema constriumo una grammatica context-free G per il linguaggio context-free A. Definiamo inoltre b il massimo numero di simboli nel lato destro di una regola. Sappiamo che in ogni albero sintattico costruito usando questa grammatica, un nodo non può avere più di b figli. Ci sono quindi al più b foglie in un passo dalla variabile iniziale, $b^2$ foglie in un due passi e così via. Quindi al passo h avremo $b^h$ foglie dalla variabile iniziale. Se l'altezza dell'albero sintattico è al più h, la lunghezza della stringa generata è $b^h$. Se invece ogni stringa generata avrà una lunghezza maggiore o uguale a $b^h+1$, ciascuno dei suoi alberi sintattici deve avere un'altezza maggiore o uguale a h+1.

Sia | V | il numero delle variabili in G. Poniamo p, la lunghezza del pumping uguale a $b^{|V|+1}$. Se s è una stringa in A e la sua lunghezza è maggiore o uguale a p, il suo albero sintattico deve avere altezza maggiore o uguale a | V | + 1, poichè $b^{|V|+1} \geq b^{|V|}+1$. Per iterare una stringa così definita, prendiamo in considerazione un suo albero sintattico $\tau$. Sappiamo che questo albero deve avere altezza maggiore o uguale a | V | + 1, quindi il suo cammino più lungo dalla radice a una foglia ha una lunghezza almeno | V | + 1. Questo cammino ha almeno | V | + 2 nodi, uno etichettato da un terminale, gli altri etichettati da variabili. Poichè G ha solo |V| variabili, qualche variabile R è presente più di una volta su questo cammino.

Dividiamo s in uvxyz, ogni occorrenza di R ha un sottoalbero sotto essa che genera una parte di questa stringa. L'occorrenza più in alto di R ha un sottoalbero più grande che genera vxy, mentre l'occorrenza più in basso genera solo x con un sottoalbero più piccolo. Entrambi questi sottoalberi sono generati dalla stessa variabile, Quindi possiamo sostituire l'uno con l'altro e ottenere ancora un albero sintattico corretto. Sostituire ripetutamente il più piccolo con il più grande fornisce gli alberi sintattici per le stringhe $uv^ixy^iz$ per ogni i > 1. Sostituire il più grande con il più piccolo genera la stringa uxz. Quindi la prima condizione del teorema è stata dimostrata.

Per dimostrare la condizione 2, dobbiamo verificare che v e y non sono entrambe $\epsilon$. Se lo fossero, l'albero sintattico ottenuto sostituendo il più piccolo sottoalbero al più grande avrebbe meno nodi di $\tau$ e genererebbe ancora s. Questo non è possibile perchè abbiamo scelto $\tau$ in modo che sia un albero sintattico per s con il più piccolo numero di nodi.

Per dimostrare la condizione 3, bisogna verificare che la lunghezza di uxy è al più p. Nell'albero sintattico per s l'occorrenza più in alto di R genera vxy. Abbiamo scelto R in modo che entrambe le occorrenze di essa cadano nelle | V | + 1 variabili più in basso del cammino e abbiamo scelto il più lungo cammino nell'albero sintattico, in modo che il sottoalbero in cui R genera vxy sia alto al più | V | + 1. Un albero con questa altezza può generare una stringa di lunghezza al più $b^{|V|+1}$ = p.

Ricapitolando quanto detto nei precedenti articoli, gli automi finiti deterministici e gli automi finiti non deterministici sono equivalenti dal punto di vista del potere riconoscitivi dei linguaggi. Gi automi a pila non deterministici invece risultano più potenti rispetto a quelli deterministici. I linguaggi che sono riconosciuti da automi a pila deterministici (DPDA) sono chiamati linguaggi context-free determiniistici (DCFL). Definire un DPDA non è semplice in quanto bisogna considerare anche le azioni che esso può compiere sulla pila. Queste $\epsilon$-mosse assumono due forme: mosse $\epsilon$-input che corrispondono a $\delta (q, \epsilon,x)$ e mosse $\epsilon$-pila che corrispondono a $\delta ( q, \epsilon, \epsilon)$. Formalmente possiamo definirlo come segue.

Definizione di automa a pila deterministico

Un automa a pila deterministico è una sestupla $(Q, \sum, \Gamma, \delta, q_0, F)$, dove:

• Q è l'insieme degli stati
• $\sum$ è l'alfabeto dell'input
• $\Gamma$ è l'alfabeto della pila
• $\delta : Q \times \sum_{\epsilon} \times \Gamma_{\epsilon} \longrightarrow (Q \times \Gamma_{\epsilon}) \cup$ { $\emptyset$ } è la funzione di transizione
• $q_0 \in Q$ è lo stato iniziale
• $F \subseteq Q$ è l'insieme degli stati accettanti

Inoltre la funzione di transizione $\delta$deve soddisfare la condizione tale che per ogni $q \in Q$, $a \in \sum$ e $x \in \Gamma$, uno di questi valori:$\delta (q,a,x)$, $\delta (q,a,\epsilon)$, $\delta q, \epsilon,x)$ e $\delta (q,\epsilon, \epsilon)$ è diverso da $\emptyset$.

Il linguaggio di un DPDA è chiamato linguaggio context-free deterministico