| Autore |
 Discussione  |
|
alucard
Nuovo Utente
Regione: Puglia
Prov.: Foggia
Città: Margherita di Savoia
|
 Inserito il - 08/12/2004 : 00:53:27
|
Salve professore...mi kiedevo se per la prova scritta del 15 dicembre 2004 c'è bisogno di prenotarsi (sono del secondo anno ed ho già superato il laboratorio). La ringrazio in anticipo...
Distinti saluti |
Si Fa Quel Ke Si Può! |
 |
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 08/12/2004 : 10:06:54
|
Citazione:
Messaggio inserito da alucard
Salve professore...mi kiedevo se per la prova scritta del 15 dicembre 2004 c'è bisogno di prenotarsi (sono del secondo anno ed ho già superato il laboratorio). La ringrazio in anticipo...
Distinti saluti
Semi mandi una mail (fabio@di.uniba.it) con il tuo nome e cognome è sufficiente |
|
|
|
aldo5000
Utente giovane
|
Inserito il - 09/12/2004 : 13:05:37
|
Salve prof!
Grazie ancora una volta !
Senta per il pumping lemma vorrei sapere come faccio a vedere se usare la catena di maggiorazione o i casi dei valori di |vwx|? Poi quando mi dice motstrare che il seguente linguaggio non è contestuale è uguale a dire libero da contesto? Per esempio si puo dimostrare che il linguaggio {a^nb^nc^m|....} non è contestuale con il pumping lemma?
Grazie anticipatamente |
|
|
|
ladylee
Utente medio
|
Inserito il - 11/12/2004 : 00:19:55
|
Salve professore avrei alcuni dubbi sugli esercizi:
1)come si risolve un esercizio quando mi chiede di dimostare che non è linerare destro;
2)dato L={ w app {a,b,c}* :w!=AaabB, A,B app {a,b,c}*} cosa rappresenta la stringa w;
3)L1={a^nb^2n:n>=0} e L2={ w app {a,b}* :|w|=5k,k>=0} stabilire se L=L1×L2 è libero da contesto. |
|
|
|
ladylee
Utente medio
|
Inserito il - 11/12/2004 : 10:33:19
|
Salve professore avrei alcuni dubbi sugli esercizi:
1)come si risolve un esercizio quando mi chiede di dimostare che non è linerare destro;
2)dato L={ w app {a,b,c}* :w!=AaabB, A,B app {a,b,c}*} cosa rappresenta la stringa w;
3)L1={a^nb^2n:n>=0} e L2={ w app {a,b}* :|w|=5k,k>=0} stabilire se L=L1×L2 è libero da contesto.
Vorrei sapere se il laboratorio è confermato per lunedi alle 15 |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 11/12/2004 : 10:46:17
|
Ciao Ladylee,
1. si risolve con il pumping lemma per i linguaggi regolari
2. w rappresenta una sequenza qualunque, anke vuota, di caratteri a o b o c
3. quale è la domanda?
Per quanto ne so io il laboratorio è confermato. |
|
|
|
ladylee
Utente medio
|
Inserito il - 12/12/2004 : 13:22:43
|
Per quanto riguarda il terzo punto cosa dovrei fare per risolverlo
|
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 12/12/2004 : 13:38:05
|
azz.
Devi dimostrare che entrambi i linguaggi sono liberi da contesto.
Ricordati che se un linguaggio è lineare destro, per il teorema della gerarchia è anche libero da contesto.
Se entrambi lo sono, per la proprietà do chiusura della concatenazione, anke L sarà libero da contesto e puoi facilmente determinarne la grammatica (cap. 5 del libro) |
|
|
|
fel
Nuovo Utente
Prov.: Bari
|
Inserito il - 13/12/2004 : 10:40:32
|
Salve professore,
Stabilire se L={a^m b^n c^k: m=n n,k>0} è libero da contesto.
Giustificare formalmente la risposta.
In questo caso non posso usare il pumping lemma, perche serve per dimostrare che non è libero.
Quindi come risolvo questo esercizio?
Grazie. |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 13/12/2004 : 11:27:59
|
A parte che la domanda della traccia non esclude la possibilità che il linguaggio non sia libero, e quindi se con il pumping lemma dimostri che non è libero la risposta sarebbe corretta. In ogni caso, in questa traccia specifica, io proverei a considerare due linguaggi, a^mb^m (m=n dalla traccia, ed entrambi maggiori di 0) e c^k (k>0 dalla traccia). Se questi due linguaggi sono liberi da contesto, allora anke la loro concatenazione lo è.
Ancora, se esiste una grammatica libera da contesto per un linguaggio L, allora il linguaggio è libero da contesto. Il problema è trovare la grammatica corretta. |
|
|
|
aldo5000
Utente giovane
|
Inserito il - 13/12/2004 : 16:43:53
|
Ok prof scusate se mi intrometto!
Per quando riguarda la domanda di Fel, come faccio a vedere cmq se un linguaggio è libero???
Inoltre se mi viene chiesto di specificare che tipo di linguaggio è L=..... come faccio?
Grazie Anticipatamente |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 13/12/2004 : 16:57:42
|
| Ciao aldo5000, se leggi la mia risposta a fel vedrai che risponde anke a te |
|
|
|
ladylee
Utente medio
|
Inserito il - 13/12/2004 : 19:50:37
|
prof grazie per avermi tolto alcuni dubbi ma ne ho degli altri:
1)come faccio a stabilire se il linguaggio X*-L è regolare
2)quando bisogna dimostrare che un linguaggio non è regolare la sottostringa che devo considerare deve avere delle caratteristiche particolari al fine dell'esercizio |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 13/12/2004 : 21:07:39
|
Ladylee, scusami ma per il primo quesito mi serve qualche informazione: Chi è X? Che linguaggio è L?
Immagino che X sia l'alfabeto su cui è definito L.
Per la seconda domanda, le caratteristiche da considerare sono quelle che derivano dalla definizione del linguaggio. Se per esempio il linguaggio fosse a^n b^n con n>0, allora la sottostringa potrebbe essere a^n oppure b^n. |
|
|
|
fel
Nuovo Utente
Prov.: Bari
|
Inserito il - 14/12/2004 : 10:41:34
|
Salve professore,
avrei un altro dubbio,
Dimostrare formalmente che il seguente linguaggio L={a^i b^j c^k : 0<=i<=j<=k} non è libero da contesto.
Vorrei sapere come risolvere questo esercizio? Dato che con il pumping lemma se ammetto che |VWX| è formata da tutte c ottengo una stringa del tipo a^p b^p c^p+k che è accettata da L in quanto c>=b.
Grazie dell' aiuto. |
|
|
|
vale
Nuovo Utente
|
Inserito il - 14/12/2004 : 11:13:49
|
Citazione:
Messaggio inserito da fel
Salve professore,
avrei un altro dubbio,
Dimostrare formalmente che il seguente linguaggio L={a^i b^j c^k : 0<=i<=j<=k} non è libero da contesto.
Vorrei sapere come risolvere questo esercizio? Dato che con il pumping lemma se ammetto che |VWX| è formata da tutte c ottengo una stringa del tipo a^p b^p c^p+k che è accettata da L in quanto c>=b.
Grazie dell' aiuto.
in questo caso penso dovresti depompare la stringa |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 14/12/2004 : 11:18:26
|
| Si infatti, vale ha ragione |
|
|
|
aldo5000
Utente giovane
|
Inserito il - 14/12/2004 : 18:22:17
|
| Salve professore vorrei sapere se è possibile trovare un grammatica di un linguaggio prima trovandomi l'automa e poi la grammatica per l'appunto!! |
|
|
|
aldo5000
Utente giovane
|
Inserito il - 14/12/2004 : 18:32:32
|
Ho un esercizio che mi chiede di trovare l'automa e la grammatica che generi il linguaggio delle stringhe senza la sottostringa papa:
posso trovarmi prima l'automa fsa e poi da li ricavarmi la grammatica?
In base a quello che ho sviluppato la grammatica dovrebbe essere:
q0 -> aq0 | bq1
q1 -> aq2 | pq1
q2 -> aq0 | pq3
q3 -> bq1 |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 15/12/2004 : 00:59:50
|
Citazione:
Messaggio inserito da aldo5000
Salve professore vorrei sapere se è possibile trovare un grammatica di un linguaggio prima trovandomi l'automa e poi la grammatica per l'appunto!!
Se è un linguaggio di classe 3 si |
|
|
|
Discussione |
|
Domande per il docente del corso B
Discussione Bloccata
