.dsy:it. - [Linguaggi Formali e Automi] Grammatiche

Pages (6): « 1 2 3 [4] 5 6 »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- [Linguaggi Formali e Automi] Grammatiche (http://www.dsy.it/forum/showthread.php?threadid=7794)

Posted by eugenio_2 on 18-01-2004 10:14:

Originally posted by rdptz

Bella domanda: perchè quella limitazione impedisce alla frase di accorciarsi dopo una produzione.

Uhm, ma perche' dobbiamo impedire alla frase di accorciarsi? E' una proprieta' che va rispettata?

In generale per quanto riguarda la dimostrazione dell'inclusione tra i vari linguaggi, bisogna dimostrare solo che l'inclusione sia propria giusto? Il fatto che siano uno sottoinsieme (improprio) dell'altro e' gia' insito nelle proprieta' delle G, che hanno regole sempre piu' stringenti; e' corretto secondo voi?

E per quanto riguarda il riconoscimento dei linguaggi: gli ASF servono solo a riconoscere L3 o possono riconoscere anche degli L2: il caso a pag.30 non si capisce se e' un caso particolare oppure se gli ASF non possono riconoscere *nessun* L2.

Tra le domande ho visto anche questa:
"Esite espressione regolare che genera un linguaggio regolare?"
Ma tutti i L denotati da espressioni regolari sono regolari, o no? Se sono denotati da regexp allora c'e' un ASF che li riconosce, e quindi sono L3 (a meno che gli ASF non riconoscano anche gli L2 - vedi sopra - allora questa considerazione non vale).

Originally posted by rdptz

hai ragione. Questo secondo me il prof. doveva chiarirlo. Qui trovi una spiegazione

Ok, grazie mille.

Posted by eugenio_2 on 18-01-2004 10:17:

Originally posted by rdptz
ops, rileggendomi noto che la mia frase può
essere fraintesa: "bella domanda" non l'ho scritto in senso ironico, cioè, non ci avevo riflettuto su quella regola prima di leggerle la tua domanda.

Ah ok, no non l'avevo assolutamente interpretata in senso ironico.

Posted by eugenio_2 on 18-01-2004 10:21:

Originally posted by xabry

17) Esempio di G3 ambigua?

Questa mi era sfuggita....mi sembra che gli esempi che fatto sulle dispense siano tutti riferiti a G2, non saprei.

Posted by rdptz on 18-01-2004 12:40:

Originally posted by xabry
Dunque.. crepi il lupo, speriamo la balena non si lasci andare, e le altre boh!! Grazie cmq!

Solo un paio di cosette:

Dallalista domande Bertoni:

17) Esempio di G3 ambigua?

credo la risposta giusta sia che non esiste una G3 ambigua, poichè le G3 sono le G generate da automi a stati finiti e un'automa a stati finiti non può essere ambiguo.

18) Esiste espressione regolare che genera linguaggio regolare?
--voleva dire denota? e la risposta è si per il Teorema di Kleene visto che linguaggio regolare è tipo 3 e quindi ric. da ASF e quindi denotato da expr. regolari?

credo proprio di sì.

21) Equazioni e incognite?
--Ok le usa per Kleene ma che gli dico? Faccio esempio a pag. 24?

piaerebbe saperlo anche a me. Io provo a guardare oggi quella parte, ch è quella più oscura (cioè non ho ben capito come passa da automa a regexp)

Posted by eugenio_2 on 18-01-2004 12:50:

Originally posted by xabry
Si io vado martedì e incrocio le dita!!!!

Sai per caso in quanti siamo Martedi?

Posted by eugenio_2 on 18-01-2004 12:54:

Originally posted by rdptz
(cioè non ho ben capito come passa da automa a regexp)

Guarda il primo esempio e ti chiarisci le idee: un'equazione per ogni stato, un prodotto nella parte dx di ogni equazione per ogni simobolo terminale, composto dal simbolo terminare x lo stato che viene raggiunto con quel simbolo terminale.
Poi risolvi il sistema.

Posted by rdptz on 18-01-2004 12:56:

Originally posted by eugenio_2
Uhm, ma perche' dobbiamo impedire alla frase di accorciarsi? E' una proprieta' che va rispettata?

non lo so, non mi sembra che le dispense parlino mai di questa proprietà. Secondo me
ha a che fare con il funzionamento dei compilatori o con qualche parte di essi.
ma è solo un'ipotesi. Non ci ho riflettuto.

In generale per quanto riguarda la dimostrazione dell'inclusione tra i vari linguaggi, bisogna dimostrare solo che l'inclusione sia propria giusto?

sì, cioè la dimo. nelle dispense dimostra quello (poi è ovvio che essere sottoinsieme proprio implica l'essere anche sottoinsieme
improprio, nel senso che la prima è una proprietà più "stringente")

E per quanto riguarda il riconoscimento dei linguaggi: gli ASF servono solo a riconoscere L3 o possono riconoscere anche degli L2: il caso a pag.30 non si capisce se e' un caso particolare oppure se gli ASF non possono riconoscere *nessun* L2.

Fai attenzione che una G3 è anche una G2 quindi a rigore è sbagliato affermare che nessuna G2 può essere riconosciuta da un ASF.
Se invece ci si chiede: un ASF può riconoscere G2 che non sono anche G3?
Boh :-) Interessante. Secondo me no.

Si potrebbe provare a inventarsi una G con una regola tipo A->aBa e vedere se la B obbliga a mantenere memoria, cosa che un ASF non può fare.

Però da quel che ho capito (speriamo Mozillax non sia troppo ottimista :-) non è richiesta tutta questa riflessione sulla materia (che poi, certo, male non fa)
Sono questioni che si possono chiarire in sede d'esame.

Posted by ale82info on 18-01-2004 13:32:

ma dall'appello di febbraio l'esame sarà scritto!? è vero o è una cazzata?! se non mi sbaglio sul sifa nella sezione dove si trovano gli appelli dei prox mesi! qualcuno sa qualcosa?!

Posted by mozilla on 18-01-2004 13:39:

Originally posted by xabry
17) Esempio di G3 ambigua?

Spontaneamente avrei detto anch'io che non esiste, ma sulle domande c'è già la risposta anche se non c'è un esempio. Sulle dispense oltretutto si dice chiaramente che una G3 ambigua esiste e che può essere trasformata nella equivalente G3 non ambigua. Un piccolissimo esempio potrebbe essere questo? A->aB , B->bC , B->b , C->epsilon

Posso generare 'ab' in due modi diversi..... :pensa:

__________________
"Direi che la signorina Lucy è più calorosa di una sposa di Giugno che cavalca nuda un cavallo senza sella in mezzo al Sahara" - Il Colono, Dracula di Francis Ford Coppola

Posted by eugenio_2 on 18-01-2004 15:27:

Originally posted by rdptz
non lo so, non mi sembra che le dispense parlino mai di questa proprietà.

Ma tu l'hai letta da qualche parte?

Originally posted by rdptz

sì, cioè la dimo. nelle dispense dimostra quello (poi è ovvio che essere sottoinsieme proprio implica l'essere anche sottoinsieme
improprio, nel senso che la prima è una proprietà più "stringente")

In realta' la dim dimostra solo ad es. che In R2 ci sono linguaggi che non ci sono in R3, e questo, *se R3 è un sottoinsieme di R2* (ma questo non viene mai provato se non indirettamente enunciando le regole di produzione delle varie G), dimostra che è un sottoinsieme proprio.

Originally posted by rdptz

Fai attenzione che una G3 è anche una G2 quindi a rigore è sbagliato affermare che nessuna G2 può essere riconosciuta da un ASF.
Se invece ci si chiede: un ASF può riconoscere G2 che non sono anche G3?
Boh :-) Interessante. Secondo me no
[....].

Si' la tua puntualizzazione e' corretta non ho esplicitato tutto il concetto perche' ero di fretta

ma in questa materia mi sa che bisogna essere molto formali.

Se tu domani vai e se hai tempo/voglia al tuo ritorno puoi fare un resoconto qua? (Se c'e' stato l'esame, come e' andato, se Martedi' c'e' Bertoni....).

Posted by rdptz on 18-01-2004 15:48:

Originally posted by eugenio_2
Ma tu l'hai letta da qualche parte?

La deduco dalle regole. Come fai ad accorciare una parola se a destra non hai mai metasimboli che "si annullano"?

E' impossibile che una produzione di Ab o di bA sia meno lunga di 2.

Se A fosse l'assioma potresti avere una regola A->e ma questa viene detto che è accettata solo se A non compare a dx di nessuna espressione (in sostanza
A->e serve solo a creare la parola vuota, non ha altre applicazioni nelle G1)

In realta' la dim dimostra solo ad es. che In R2 ci sono linguaggi che non ci sono in R3, e questo, *se R3 è un sottoinsieme di R2* (ma questo non viene mai provato se non indirettamente enunciando le regole di produzione delle varie G), dimostra che è un sottoinsieme proprio.

Sì in effetti mi sa che hai ragione e che è più corretto vederla così. Dimostro che sono sottoinsiemi propri e parto dall'assunto che siano sottoinsiemi (assunto, che è evidente di per sè guardando le regole: "chiaramente le G di tipo K sono un sottinsieme ... ")

Se tu domani vai e se hai tempo/voglia al tuo ritorno puoi fare un resoconto qua? (Se c'e' stato l'esame, come e' andato, se Martedi' c'e' Bertoni....).

sì sì, io vado salvo catastrofi. Vi faccio sapere.

Posted by xabry on 18-01-2004 16:12:

Originally posted by eugenio_2
[BIn generale per quanto riguarda la dimostrazione dell'inclusione tra i vari linguaggi, bisogna dimostrare solo che l'inclusione sia propria giusto? Il fatto che siano uno sottoinsieme (improprio) dell'altro e' gia' insito nelle proprieta' delle G, che hanno regole sempre piu' stringenti; e' corretto secondo voi?[/B]

Si secondo me si anche perchè altrimenti non basterebbe dim. per un linguaggio preciso ma dovrebbe dimostrarlo in modo generale per tutti!

Posted by xabry on 18-01-2004 16:13:

Originally posted by eugenio_2
Sai per caso in quanti siamo Martedi?

Non ne ho idea!

Posted by eugenio_2 on 18-01-2004 20:40:

Qualcuno sa come si svolgono operativamente gli esami di Bertoni: fa un appello prima? L'ordine lo decide lui? E' un problema se si arriva in ritardo (i treni non sempre sono puntuali )?

Posted by mozilla on 18-01-2004 22:39:

Originally posted by eugenio_2
Qualcuno sa come si svolgono operativamente gli esami di Bertoni: fa un appello prima? L'ordine lo decide lui? E' un problema se si arriva in ritardo (i treni non sempre sono puntuali )?

L'anno scorso aveva preso i nomi, il primo che glielo diceva lui lo scriveva. Aveva dovuto dividerci in più gruppi perchè eravamo tanti, il giorno dell'esame non ricordo se rifà l'appello, però da la precedenza a quelli che hanno esigenze particolari. In generale è molto tranquillo, quindi anche se dovessi arrivare in ritardo non penso che si infervori :swear:

Un consiglio, non mettete magliette con scritto E=mc^2 : lui è un fisico, vi chiederebbe di discuterla! :-D

__________________
"Direi che la signorina Lucy è più calorosa di una sposa di Giugno che cavalca nuda un cavallo senza sella in mezzo al Sahara" - Il Colono, Dracula di Francis Ford Coppola

All times are GMT. The time now is 09:19.

Pages (6): « 1 2 3 [4] 5 6 »
Show all 86 posts from this thread on one page