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 concetti di albero di derivazione, lunghezza di un cammino lungo un albero, altezza di un albero e il principio di sostituzione.

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

1. S → Ha → HSa → aSa → aHaa → aaaa (derivazione sinistra espandendo il NT + a sinistra)
2. S → Ha → HSa → HHaa → Haaa → aaaa (derivazione destra espandendo il NT + a destra)

L'indiscrezione su quale sequenza sia stata applicata scompare se consideriamo l'albero di derivazione della stringa aaaa secondo la grammatica G, infatti guardandolo non

siamo1capaci 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.

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

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

1. la radice è etichettata con il simbolo iniziale S;
2. ogni nodo interno (nodo non foglia) è etichettato con un simbolo di V (è un non terminale); nodo foglia è etichettato con un simbolo di X (un terminale) oppure con λ;
3. ogni , ... , N
4. se un nodo N è etichettato con A, ad N ha k discendenti diretti (nodi

figli) N , N , etichettati con1 2 k, … , A …Ai simboli A , A rispettivamente, allora la produzione A→A A deve appartenere a P;1 2 k 1 2 kla stringa w può essere ottenuta leggendo (e concatenando) le foglie dell’albero da sinistra a destra.

5-Ora che abbiamo capito cosa è un albero di derivazione possiamo chiarire i concetti di lunghezza di uncammino e profondità o altezza. La lunghezza di un cammino dalla radice ad una foglia è pari al numero di nonterminali 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è 3 ( S H S ) ed infine il cammino dell’ultimacammino per la seconda a è pari a 4 ( S H S H ), per la terza a aL’altezza dell’albero (o profondità) è determinata dalla(quella più a destra)

è 1, infatti si incontra solo la S.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: 1- S => 0B => 00BB => 001B => 0011 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 nonterminale 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 (che produce 011), racchiuso nel cerchio tratteggiato e quello con radice nella B in basso (che produce questa operazione dobbiamo "potare" il 1), racchiuso nel cerchio continuo. Per eseguire sottoalbero inferiore ed "innestarci" quello superiore. Il risultato è riprodotto nella figura qui a sinistra. L'albero ottenuto è un albero valido per la stringa 000111. Notiamo che la stringa ottenuta con questa operazione è ancora una parola che appartiene al linguaggio di partenza, infatti ha un numero uguale di 0 e di 1. Inoltre l'altezza dell'albero è

variatapassando da 3 a 4 (senza considerare la B ripetuta) ed anche la lunghezza della frontiera è aumentata da 4 a 6. Possiamo ripetere questa sostituzione un numero di volte arbitrarioottenendo sempre stringhe appartenenti al linguaggio.

0011 |w| = 4000111 |w| = 600001111 |w| = 8. .. .. .|w| = 2n+2 n = 1,2,…n n00 11

Anche apportando la sostituzione inversa, cioè potando il sottoalbero superiore edinnestandoci quello inferiore, otteniamo ancora una parola valida coma mostrato nellafigura in basso di fianco.

Da questo esempio possiamo dedurre che la lunghezza delle parole di un linguaggio CFcresce in maniera costante, o perlomeno un sottoinsieme delle parole. Siamo quindi giuntia dire che possiamo sostituire sottoalberi di altezza diversa purché abbiano come radice lostesso simbolo non terminale (stiamo parlando sempre di alberi di derivazione per unastringa di un linguaggio CF altrimenti non lo potremmo fare!). Allora se un linguaggio ècostituito da

Parole che non crescono in maniera costante possiamo subito escludere che sia libero da contesto. Riflettiamo un po' su quello che abbiamo fatto. Abbiamo cercato in un albero di derivazione corretto due occorrenze di uno stesso non terminale lungo un cammino, che siano radici di due sottoalberi di altezza diversa. Ma come facciamo ad essere sicuri che un albero di derivazione contenga almeno due occorrenze di uno stesso non terminale? Mmmm... è abbastanza semplice, sarebbe come dire: "se ho 5 palle rosse e 50 palle blu in un sacchetto, come faccio ad essere sicuro di prendere due palle dello stesso colore?" (ovviamente senza vedere!) Qualcuno potrebbe dire "le prendo tutte! :-)" oppure "51" oppure "6". La risposta migliore invece è 3. Infatti prendo la prima e può essere o rossa o blu, prendo la seconda ed avrò in mano o 1 rossa e 1 blu, o se sono un po' fortunato...

2 rosse o 2 blu, ma non posso esserne sicuro. Estraendo la terza avrò 2 rosse e 1 blu, o 2 blu e 1 rossa, e se sono molto fortunato 3 rosse o 3 blu, sono comunque sicuro di avere due palle dello stesso colore.

Vediamo questo esempio da un punto di vista grafico:

prima estrazione: R o B

seconda estrazione R -> R o B -> RR -> B o B -> B

terza estrazione R -> R -> R o B -> R -> RR -> R -> B o B -> R -> BR -> B -> R o B -> B -> RR -> B -> B o B -> B -> B

A questo punto vi sarete chiesti “ma cosa c’entra tutto questo col principio di sostituzione?”

Ecco la risposta: immaginate che le sequenze sopra scritte rappresentiano una sequenza di derivazione, la struttura è simile a quella di un albero di derivazione (messo orizzontalmente) dove i colori sono i simboli nonterminali R e B.

Allora, non avete ancora capito il nesso?

Sono necessarie due estrazioni perché i colori sono 2, se ci fossero stati 10

colori e volevamo essere sicuri di pescare 2 palle dello stesso colore avremmo dovuto fare 11 estrazioni. Analogamente se voglio essere sicuro che un albero contenga almeno un non terminale ripetuto devo scegliere un albero la cui altezza sia maggiore del numero di non terminali, cioè altezza(albero) > n con |V|=n, quindi basta scegliere un albero con altezza pari a n + 1 dove n è la cardinalità dei non terminali. Generalizziamo ora il discorso per qualsiasi albero di derivazione. Supponiamo di avere un albero di derivazione Tz per una stringa z di terminali, generata da una grammatica G libera da contesto e supponiamo che il non terminale A sia ripetuto due volte su un cammino. L'albero sarà che il non terminale A sia ripetuto del tipo di quello di fianco. Possiamo notare che il sottoalbero con radice nella A più in basso genera la sottostringa w, mentre quello con radice nella A più in alto genera la sottostringa vwx, la stringa generata da S è invece uvwxy. Poiché

la grammatica è di tipo CF possiamo effettuare la sostituzione dei sottoalberi: sostituendo il sottoalbero superiore con quello inferiore otteniamo la stringa uwy, mentre con la sostituzione inversa otteniamo un albero valido per la stringa uvvwxxy ( = uv wx y ). Ripetendo questa operazione un numero finito di volte otteniamo tutte le stringhe nella forma ≥ 0.n nuv wx y con n

Soffermiamoci un attimo sul metodo di scelta del NT ripetuto sul cammino e vediamo alcuni esempi. Bisogna considerare la coppia di non terminali ripetuta per ultima! Quindi:

S
|
S
|
S
/ \
/ \
/ \
S C A C A C A S
/ \
| |
| |
| |
| |
| |
/ \
B A a A a B a B
B B A
| |
| |
| |
| |
| |
b A B B A a B
| |
| |
| |
| |
a B A B a
| |
| |
| |
b b b

I non terminali scritti in rosso sono quelli che devono essere scelti come ripetuti lungo un cammino. Nell'ultimo esempio non ci sono NT ripetuti perché le due B sono su due cammini differenti. L'ultima premessa da fare è la relazione tra altezza di un albero e lunghezza della parola alla sua

frontiera.
Consideriamo la solita grammatica CF e denotiamo con m la massima lunghezza tra tutte le parti destre delle produzioni di P che in formule diventa: m = max{|w| | A→ w}
Ad esempio se P = {S→1|AB, A→00S, B→1} m = 3 perché la più lunga parte destra è 00S ed è lunga 3.
Se l'altezza di tale albero è al più uguale a j allora |w| ≤ m cioè: se l'altezza dell'albero è minore o uguale a j allora la lunghezza della parola è minore o uguale a m.
Sarebbe equivalente scrivere che |w| > m => height(T) > j, cioè: se una parola è più lunga di m allora il suo albero di derivazione deve avere obbligatoriamente un'altezza maggiore di j.