Pumping Lemma per i linguaggi liberi da contesto - Spiegazione

Pumping lemma per i linguaggi liberi da contesto

Prima di poter definire il Pumping Lemma per i Linguaggi Liberi da contesto è necessario prima avere chiari i concetti di albero di derivazione, lunghezza di un cammino lungo un albero, altezza di un albero e il principio di sostituzione.

Albero di derivazione

Un albero di derivazione è la rappresentazione univoca di una sequenza di produzioni. Ad esempio → (1) (2) (3) considerando la grammatica G₁ con P = {S→Ha, H→HS, H→a} e volendo derivare la stringa aaaa è possibile procedere in due modi:

• Derivazione 1 - S => Ha => HSa => aSa => aHaa => aaaa (derivazione sinistra espandendo il NT più a sinistra).
• Derivazione 2 - S => Ha => HSa => HHaa => Haaa => aaaa (derivazione destra espandendo il NT più a destra).

L’indecisione su quale sequenza sia stata applicata scompare se consideriamo l’albero di derivazione della stringa aaaa secondo la grammatica G₁, infatti guardandolo non siamo capaci di decidere se abbiamo espanso prima il NT H o S (nel punto indicato dalla freccia).

Da questo esempio possiamo dedurre che data una derivazione possiamo costruire un solo albero di derivazione corrispondente, invece, dato un albero di derivazione esso corrisponderà a più derivazioni in funzione dell’ordine in cui saranno espansi i non terminali.

Definizione di albero di derivazione

La definizione di albero di derivazione (riportata sul libro) è la seguente:

Sia G = (X, V, S, P) una grammatica libera da contesto e w ∈ X* una stringa derivabile da S in G. Dicesi albero di derivazione l’albero T avente le seguenti proprietà:

• Punto 1 - La radice è etichettata con il simbolo iniziale S;
• Punto 2 - ogni nodo interno (nodo non foglia) è etichettato con un simbolo di V (è un non terminale);
• Punto 3 - ogni nodo foglia è etichettato con un simbolo di X (un terminale) oppure con λ;
• Punto 4 - se un nodo N è etichettato con A, ed N ha k discendenti diretti (nodi figli) N₁, N₂, …, N_k, etichettati con A₁, A₂, …, A_k rispettivamente, allora la produzione A→A₁A₂…A_k deve appartenere a P;
• Punto 5 - la stringa w può essere ottenuta leggendo (e concatenando) le foglie dell’albero da sinistra a destra.

Lunghezza di un cammino e altezza

Ora che abbiamo capito cosa è un albero di derivazione possiamo chiarire i concetti di lunghezza di un cammino e profondità o altezza. La lunghezza di un cammino dalla radice ad una foglia è pari al numero di non terminali su quel cammino. Ad esempio considerando l’albero precedente per la derivazione della stringa aaaa, il cammino per la prima a (quella più a sinistra) è pari a 3 perché si incontra prima S, poi H ed ancora H, il cammino per la seconda a è pari a 4 (S H S H), per la terza a è 3 (S H S) ed infine il cammino dell’ultima (quella più a destra) è 1, infatti si incontra solo la S.

L’altezza dell’albero (o profondità) è determinata dalla lunghezza del cammino più lungo, quindi la profondità dell’albero considerato precedentemente è 4.

Principio di sostituzione dei sottoalberi

Consideriamo la grammatica G libera da contesto con le seguenti produzioni P = {S→0B|1A; A→0|0S|1AA; B→1|1S|0BB}, tale grammatica genera tutte e sole le stringhe che hanno un numero uguale di 1 e di 0 (esercizio 2.2 pag. 36 del libro). Consideriamo la stringa 0011, essa è ottenibile attraverso due derivazioni:

• Derivazione 1 - S => 0B => 00BB => 001B => 0011.
• Derivazione 2 - S => 0B => 00BB => 00B1 => 0011.

Come detto precedentemente il non determinismo scompare quando consideriamo l’albero di derivazione per questa stringa. L’albero è riportato qui di seguito.

Adesso consideriamo il sottoalbero con radice nella B più in alto (racchiuso nel cerchio). Esso ha come frontiera (insieme delle foglie) la stringa 011. Possiamo quindi affermare che partendo dal non terminale B è possibile produrre la stringa 011. Poiché la grammatica G è libera da contesto possiamo sostituire un non terminale con una sua produzione indipendentemente dal contesto, quindi possiamo sostituire liberamente qualsiasi occorrenza di B con 011.

Effettuiamo questa sostituzione tra il sottoalbero con radice nella B in alto (c