 |
puntozip |
.arcimaestro.
Registered: Jan 2003
Posts: 332 (0.04 al dì)
Location: milano
Corso: Ticom
Anno: 1
Time Online: 10 Days, 4:57:16 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by Alessandra
Ciao a tutti,
sto studiando le "dispense allucinanti" per l'appello di settembre,
... qualche super tecnicone saprebbe spiegare in parole umane comprensibili cos'è un pumping lemma?
Grazie1000
Premesso che sono quanto di più lontano possa esserci da un "super tecnicone" e che concordo sul fatto che il pumping lemma sia da imparare a memoria, vediamo se riesco a togliere almeno un po' di nebbia.
1) occorre che tu abbia chiari i concetti di albero di derivazione, altezza di un albero e di grammatica di tipo 2 in forma normale di chomsky, perche la dim. si basa su di essi.
2) l'enunciato lo devi proprio imparare a memoria, non è ovviamente possibile semplificarlo...
A cosa serve il P.L.? A dimost. che un dato linguaggio non è di tipo 2, infatti esprime una condizione necessaria affinchè un Ling. sia di tipo 2 ma non suff. quindi se un linguaggio soddisfa il P.L. non puoi dire che sia di tipo 2 ma se non lo soddisfa allora sicuramente non è di tipo 2.
Passiamo alla dim.
Il teorema ti dice di fissare un valore H, tale valore non è arbitrario ma è legato al linguaggio L, infatti un linguaggio di tipo 2 ammette sempre una grammatica di tipo 2 che lo genera e che puoi considerare nella forma normale di Chomsky (così puoi creare un albero di derivazione binario per le parole del ling.).
Come sai una grammatica è contraddistinta da delle regole di produzione e da un certo numero di metasimboli, il valore di H è determinato proprio da questo numero, è infatti uguale a 2 ^ |M| + 1.
(|M| è la cardinalità dell'insieme dei metasimboli della ns. grammatica). Poniamo per semplicità di scrittura: h = |M|
A questo punto prendi una parola qualsiasi del linguaggio (es. z) che abbia lung. z > di H e disegna il suo albero di derivazione. Tale albero avrà l'assioma come radice, un certo numero di metasimboli come nodi intermedi e le foglie saranno i simboli terminali che compongono z.
Il numero di foglie di un albero binario è in relazione con la sua altezza, infatti l'altezza è almeno il logaritmo in base 2 del numero di foglie, ma il numero di foglie è anche la lunghezza di z quindi:
|z| > H e altezza albero >= log |z| => altezza albero > log H => altezza albero > h + 1.
L'altezza di un albero è la lunghezza del ramo più lungo, quindi ci sarà un percorso dall'assioma a un simbolo terminale più lungo di h+1, tale lunghezza è determinata dal numero di metasimboli compresi tra l'assioma e il terminale.
Noi abbiamo però solo h metasimboli a disposizione per cui se ci limitiamo anche agli ultimi h+1 nodi del percorso dovremo ripetere almeno un metasimbolo...
Fine prima parte - spero che fin qui sia chiaro (e corretto...).
A più tardi
__________________
There are two ways of constructing a software design:
one way is to make it so simple that there are obviously no deficiencies;
the other way is to make it so complicated that there are no obvious deficiencies.
(C.A.R. Hoare)
|
Alessandra
