| V I S U A L I Z Z A D I S C U S S I O N E |
| marijuana |
Inserito il - 07/02/2007 : 14:55:30
Ho scritto la definizione di Pumping Lemma per i Linguaggi Liberi da Contesto su Wikipedia Italia.
http://it.wikipedia.org/wiki/Pumping_lemma_per_i_linguaggi_context_free
Dateci no sguardo, e' la traduzione di quella inglese.. non so'.. puo' esser utile a capire cosa ci si aspetta dal pumping lemma.. |
| 5 U L T I M E R I S P O S T E (in alto le più recenti) |
| fabbattista |
Inserito il - 08/02/2007 : 14:47:03
ciao ivan (non ti divertire troppo dove ti trovi),
anche se il wiki è fatto per essere modificato da chiunque non mi permetterei mai di mettere mani nel lavoro di altri, e poi sono troppo pigro per farlo....:)
marijuana, intendo un esercizio del tipo
Dimostrare che il seguente lihguaggio L={a^j b^k c^w | i<=k<=w} non è libero.
La cardinalità di z parola di L non è importante quanto valga, basta solo che sia maggiore di p. Il fatto di sceglere tutti e 3 gli esponenti uguali al valore p garantisce che la cardinalità di z sia 3p (quindi maggiore di p) e facilita la soluzione del problema (basta che la stringa pompata aumenti di un solo simbolo per violare le condizioni del linguaggio)
Una fonte sicura potrebbe essere quella costituita dal prof. i giorni di ricevimento.
A quanto ne so gli archeologi non hanno trovato alcuna stele riportante la dimostrazione del pumping lemma, ma non mi meraviglierei se dovesse succedere. Fino a quando non avverrà il ritrovamento, la maggior parte dei testi sui linguaggi formali ne parlano. |
| marijuana |
Inserito il - 08/02/2007 : 00:26:39
Citazione:
Messaggio inserito da marijuana
grazie per la dritta fabba.. ora gli do na sistemata ed aggiungo l'altra dimostrazione.. che e' troppo evil. Se scrivo qualche altra imprecisione eo cagata colossale per favore segnalamelo.. non vorrei esser causa della bocciatura di milioni di aspiranti informatici.. anche se.. meno concorrenza..
punto di domanda: per relazione di uguaglianza intendi un esercizio del tipo: Dimostra che L={a^j b^k c^w | i,k,w > 0} ? No perche', in quel caso: MICA HO CAPITO! cioe'.. sul libro del professor semeraro non c'e' un esempio del genere.. ed il libro l'ho letto cosi' tante volte che non aver capito come fare mi fa sentire abbastanza idiota..
suppongo che la cardinalita' di z parola di L possa essere benissimo 3p (con p dipendente solo bla bla bla nella dimostrazione) ma non ho trovato, o non ho ben interpretato questo caso specifico.
c'e' qualche altra risorsa per questa cosa? un manoscritto.. delle incisioni nell'argilla? il 16 devo ridare lo scritto perche' il 2 sono stato bellamente bocciato proprio per una traccia simile. |
| marijuana |
Inserito il - 07/02/2007 : 23:55:40
grazie per la dritta fabba.. ora gli do na sistemata ed aggiungo l'altra dimostrazione.. che e' troppo evil. Se scrivo qualche altra imprecisione eo cagata colossale per favore segnalamelo.. non vorrei esser causa della bocciatura di milioni di aspiranti informatici.. anche se.. meno concorrenza.. |
| ivan |
Inserito il - 07/02/2007 : 21:40:08
Citazione:
Messaggio inserito da fabbattista
Ci sarebbero 2 imprecisioni.
Nel punto 2 dell'esercizio p puo' essere anche uguale a j, visto che comunque z avrà lunghezza maggiore di p
Nel punto 3 dell'esercizio, quando scrivi "ogni occorrenza di vwx in a^jb^jc^j" credo tu debba scrivere "a^pb^pc^p"
Infine, nel punto 4 dell'esercizio quando scrivi "posto che al piu' una tra v ed y e' la stringa vuota", sembra che tu possa decidere di non porre questa condizione. Invece, i valori di v e y non DEVONO essere entrambi nulli a causa della seconda delle condizioni a cui deve sottostare un linguaggio libero.
Un suggerimento: metti un esercizio diverso in cui ci siano relazioni non di uguaglianza tra i 3 esponenti, altrimenti non ci si rende conto che spesso la soluzione è un po' piu' complessa.
fabba correggi tu direttamente no?
|
| fabbattista |
Inserito il - 07/02/2007 : 21:35:02
Ci sarebbero 2 imprecisioni.
Nel punto 2 dell'esercizio p puo' essere anche uguale a j, visto che comunque z avrà lunghezza maggiore di p
Nel punto 3 dell'esercizio, quando scrivi "ogni occorrenza di vwx in a^jb^jc^j" credo tu debba scrivere "a^pb^pc^p"
Infine, nel punto 4 dell'esercizio quando scrivi "posto che al piu' una tra v ed y e' la stringa vuota", sembra che tu possa decidere di non porre questa condizione. Invece, i valori di v e y non DEVONO essere entrambi nulli a causa della seconda delle condizioni a cui deve sottostare un linguaggio libero.
Un suggerimento: metti un esercizio diverso in cui ci siano relazioni non di uguaglianza tra i 3 esponenti, altrimenti non ci si rende conto che spesso la soluzione è un po' piu' complessa. |
