| Autore |
 Discussione  |
|
|
micur
Nuovo Utente
Regione: Puglia
Prov.: Bari
|
 Inserito il - 12/07/2010 : 17:48:11
|
|
gente ho qualche domanda su questi esercizi e spero che qualcuno mi risponda... negli esempi sulle dispense di semeraro ci sono alcuni esercizi che usano il pumping lemma sui linguaggi liberi da contetesto in cui si analizza la sottostringa vwx (per es. se è formato da tutte a, se è formato da tutte b...) e in altri no, come faccio a capire dove devo analizzare la sottostringa e dove no? poi lì ci sono solo esercizi in cui ci sono solo linguaggi non context free e dimostrare che non lo siano, e se ci sono es in cui ci sono linguaggi context free? ultima cosa qualcuno riesce a dimostrare che il linguaggio L={a^n b^k, con n>0 e k>n} è context free?
|
|
|
kelly
Nuovo Utente
|
 Inserito il - 13/07/2010 : 14:21:26
|
La prima condizione necessaria perchè un linguaggio sia libero da contesto è che le parola che lo caratterizzano crescano secondo una costante, es: sappiamo che L={a^n b^n|n>=0} è un linguaggio C.F., se analizziamo le sue parole otteniamo L= {lambda,ab,aabb,aaabbb,aaaabbbb,....}le lunghezze delle parole sono 0,2,4,6,8..... crescono secondo la costante 2.
Per svolgere gli esercizi del pumping lemma prova a verificare prima se le parole crescono secondo questa costante, quindi devi procedere col metodo della composizione della sottostringa vwx, se questa costante non esiste devi procedere ragionando sulle lunghezze delle stringhe come è indicato nel libro.
Quando l'esercizio ti chiede di dimostrare che il linguaggio non è libero lo devi dimostrare col pumping lemma, quando invece ti chiede di verificare se il linguaggio è libero o meno allora dovresti vedere se esiste una grammatica libera da contesto che genera quel linguaggio, se esiste il linguaggio è C.F., il pumping lemma serve solo per dimostrare che un linguaggio non è libero e non per dimostrare che lo è.
Per quanto riguarda L={a^n b^k, con n>0 e k>n} per dimostrare che il linguaggio è context free devi trovare una grammatica context free che lo generi. |
Modificato da - kelly in data 13/07/2010 14:23:22 |
 |
|
|
micur
Nuovo Utente
Regione: Puglia
Prov.: Bari
|
Inserito il - 15/07/2010 : 11:26:12
|
grazie della risposta, comunque mi ero già accorto, subito dopo aver postato la domanda, che il pumping lemma serviva a dimostrare che un linguaggio NON è libero da contesto e non il contrario.
inoltre so già che un linguaggio affinchè sia libero da contesto deve avere almeno un sottoinsieme di parole che crescono in modo costante, ma qui sorge un nuovo terribile dubbio!!! tra gli esercizi svolti c'è la dimostrazione sempre tramite pumping lemma che la grammarica a^n b^n c^n non è libera da contesto!!! ma se la lunghezza di questa parola è 3n??? non cresce in modo costante anche questo linguaggio??? |
|
|
|
kelly
Nuovo Utente
|
Inserito il - 16/07/2010 : 16:21:17
|
| Il fatto che in un linguaggio le parole crescano secondo una costante è una caratteristica dei linguaggi context free, ed è una condizione necessaria ma non sufficente per capire se un linguaggio è c.f. o meno. a^n b^n c^n ha un sottoinsieme di parole che crescono in maniera costante ma è dimostrato che non è c.f. perchè non esiste una grammatica c.f. che lo generi. |
|
|
| |
Discussione |
|
|
|
esercizi sul pumping lemma
