.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- [LFA] Informazioni A.A. 2003/04 (http://www.dsy.it/forum/showthread.php?threadid=12101)
Posted by Alessandra on 13-09-2004 17:28:
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
Posted by khelidan on 13-09-2004 18:22:
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
Il Punping lemma....non so in quanti l'abbiano capito,io di certo no!!
__________________
Khelidan
Posted by ghily on 13-09-2004 19:45:
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
il pumping lemma è uno dei grandi misteri di lfa.Puoi solamente impararlo a memoria e sperare che non te lo chieda.
In bocca a lupo
chao
roby
Posted by puntozip on 14-09-2004 08:45:
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)
Posted by Alessandra on 14-09-2004 17:57:
Ah... gasp... ho capito,
grazie a tutti per la spiegazione, speriamo che non lo chieda..sob
