.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 xabry on 17-01-2004 08:13:

Grazie Mozilla mi hai chiarito molte cose!

Approfitto ancora:

1)Nella Dim. di inclusione dei linguaggi sostiene che anbn (scusa se lo scrivo così) non appartiene ad R3. Dice che lo mostrerà in seguito. La ragione è quella indicata a pag 17 Esempio 3.3?

2) Nella dim del Pumping Lemma (evvai che quasi quasi mi è chiaro) ho qualche dubbio sul punto 2 in fondo a pagina 29.
La lunghezza della parola coincide con il numero di foglie? Ma una foglia è associata sempre a un singolo simbolo o solo in questo caso per la composizione scelta?

Ti ringrazio e "io speriamo che me la cavo"!!!!!
Ciao :sad:

Posted by mozilla on 17-01-2004 12:19:

Originally posted by xabry
Grazie Mozilla mi hai chiarito molte cose!

Approfitto ancora:

1)Nella Dim. di inclusione dei linguaggi sostiene che anbn (scusa se lo scrivo così) non appartiene ad R3. Dice che lo mostrerà in seguito. La ragione è quella indicata a pag 17 Esempio 3.3?

2) Nella dim del Pumping Lemma (evvai che quasi quasi mi è chiaro) ho qualche dubbio sul punto 2 in fondo a pagina 29.
La lunghezza della parola coincide con il numero di foglie? Ma una foglia è associata sempre a un singolo simbolo o solo in questo caso per la composizione scelta?

Si, la parola la si ottiene semplicemente leggendo da sinistra a destra le foglie dell'albero, le quali contengono ciascuna un solo simbolo terminale.

In bocca al lupo, in culo alla balena, tra le palle del grillo e le tette della formica a TUTTI! :-D

(queste non le sapevate eh....!)
:cool:

__________________
"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 17-01-2004 13:10:

Originally posted by mozilla

Sicuramente ha invertito w con q. In questo caso definisce induttivamente la funzione di transizione, definendo la composizione della funzione, quindi se tu hai dato in ingresso una parola w e poi gli dai un termine sigma_piccolo, è come se gli dassi in una volta sola w+sigma_piccolo (+ nel senso di concatenazione).

Ci siamo, ma mi sfugge in generale il significato corretto di "definire per induzione" o "dimostrare per induzione".

Posted by eugenio_2 on 17-01-2004 13:21:

Originally posted by mozilla

Si, la parola la si ottiene semplicemente leggendo da sinistra a destra le foglie dell'albero, le quali contengono ciascuna un solo simbolo terminale.

Ok, ma allora perche' nel primo paragrafo della dim dice che la derivazione di Z ha H foglie? Dovrebbe averne almeno H+1 essendo |z|>H giusto?

Originally posted by mozilla
In bocca la lupo, in culo alla balena, tra le palle del grillo e le tette della formica a TUTTI! (queste non le sapevate eh....!)

Crepi, grazie.

Posted by eugenio_2 on 17-01-2004 13:23:

Originally posted by xabry
Grazie Mozilla mi hai chiarito molte cose!

[....]

Ti ringrazio e "io speriamo che me la cavo"!!!!!
Ciao

Xabry tu dai l'esame martedi' 20?

Posted by mozilla on 17-01-2004 13:45:

Originally posted by eugenio_2
Ci siamo, ma mi sfugge in generale il significato corretto di "definire per induzione" o "dimostrare per induzione".

Dalla matematica si definisce per induzione (o si dimostra) quando si dimostra una certa cosa col passo base per n=1, lo si considera vero per qualsiasi n, e quindi lo si dimostra per n=n+1. E' molto approssimativa come spiegazione, comunque ricordo di averla fatta in Matematica Discreta, e poi la si riprende in molte materie.

__________________
"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 mozilla on 17-01-2004 14:09:

Originally posted by eugenio_2
Ok, ma allora perche' nel primo paragrafo della dim dice che la derivazione di Z ha H foglie? Dovrebbe averne almeno H+1 essendo |z|>H giusto?

Questa cosa mi sfugge..... non è che quando dice che esiste un albero di der. con H foglie non intende finale, ma durante la derivazione?

__________________
"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 rdptz on 17-01-2004 14:22:

Originally posted by eugenio_2
Ok, ma allora perche' nel primo paragrafo della dim dice che la derivazione di Z ha H foglie? Dovrebbe averne almeno H+1 essendo |z|>H giusto?

Boh, in effetti è così. La proposizione "esiste un'albero di derivazione con H foglie" a rigore è scorretta se la parola è più lunga di H.

Forse la scorrettezza di quella frase non è importante perchè quello che conta ai fini della dimostrazione è che:

h = numero metasimboli
H = 2^(h+1)
Lunghezza del cammino >= h+1 ( o >= log H)

Quindi un metasimbolo è ripetuto perchè,
poniamo ci siano 2 meta e il cammino sia 3:

Nodo1--Nodo2--Nodo3--Nodo4

Il cammino sopra è lungo 3, abbiamo Nodo4 che è la foglia, e tre metasimboli quindi uno dei 2 è ripetuto.

Sbaglio? (lo sto preparando anch'io quindi potrei aver scritto una boiata)

-------------------------

Ah, avrei anch'io un paio di dubbi (ne ho di più ma mi limiterò)

1) relativamente all'automa a pila, non capisco perchè nella dispensa non parli mai degli stati (q0, q1, ...) . La descrizione torna comunque, ma nel testo di Hocrpft gli automi a pila vengono descritti in termini di stati.

2) all'esame utilizza gli esempi della dispensa o ti pone davanti a linguaggi improvvisati al momento?
Finchè si tratta di passare dalla G3 all'automa e viceversa, o di trasformare in GNF o CNF (le forme normali) ok, applicare il ragionamento a qualsiasi L può essere relativamente semplice, ma io già su un domanda tipo: dato questo linguaggio (non il solito a^n-b^n-c^n) usa il pumping lemma per dimostrare che non è context-free andrei un pelo in difficoltà.

Oppure: preso un linguaggio a caso: "è generabile da una G di tipo N"?

Posted by mozilla on 17-01-2004 17:13:

Originally posted by rdptz
.....Sbaglio?

Secondo me non sbagli, però come dicevo sopra il pumping lemma mi sfugge un po' quindi non ci giurerei.

1) relativamente all'automa a pila, non capisco perchè nella dispensa non parli mai degli stati (q0, q1, ...) . La descrizione torna comunque, ma nel testo di Hocrpft gli automi a pila vengono descritti in termini di stati.

Bertoni gli automi a pila ce li ha descritti come un nastro su cui c'è memorizzata una stringa di caratteri (la parola da riconoscere) e uno stack (la pila appunto) in cui mette e toglie i metasimboli fino a dimostrare che la parola è riconosciuta dal linguaggio o no.

2) all'esame utilizza gli esempi della dispensa o ti pone davanti a linguaggi improvvisati al momento?
Finchè si tratta di passare dalla G3 all'automa e viceversa, o di trasformare in GNF o CNF (le forme normali) ok, applicare il ragionamento a qualsiasi L può essere relativamente semplice, ma io già su un domanda tipo: dato questo linguaggio (non il solito a^n-b^n-c^n) usa il pumping lemma per dimostrare che non è context-free andrei un pelo in difficoltà.
Oppure: preso un linguaggio a caso: "è generabile da una G di tipo N"?

A me personalmente ha chiesto solo la dim. di inclusione dei linguaggi. Oltretutto non è assolutamente cattivo, gli esempi se li fa fare a te, puoi fare quelli che vuoi.
Comunque per quello che vedo, riferendomi a voi 3 o 4 che state usando il forum, mi sembrate abbastanza preparati. A Luglio ho visto un paio di persone che non sapevano quasi nulla, e quel poco che sapevano era pure sbagliato, lui con aria sconsolata dice "...eh, mi dispiace ma..." e io dentro di me "adesso lo canna, del resto ci sta tutto..." e lui "...più di 23 non posso darle"!
:shock:

Comunque sugli esempi non fatevi problemi, l'importante è che magari ne abbiate uno pronto per ogni tipo di linguaggio.

__________________
"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 17-01-2004 17:32:

Originally posted by rdptz

2) all'esame utilizza gli esempi della dispensa o ti pone davanti a linguaggi improvvisati al momento?
Finchè si tratta di passare dalla G3 all'automa e viceversa, o di trasformare in GNF o CNF (le forme normali) ok, applicare il ragionamento a qualsiasi L può essere relativamente semplice, ma io già su un domanda tipo: dato questo linguaggio (non il solito a^n-b^n-c^n) usa il pumping lemma per dimostrare che non è context-free andrei un pelo in difficoltà.

Oppure: preso un linguaggio a caso: "è generabile da una G di tipo N"?

Si' spero anch'io che non faccia domande di questo tipo o cmq si limiti a linguaggi "noti"....GNF CNF cosa intendi?

A me e' venuto un dubbio madornale: le grammatiche di tipo 1 possono contenere regole di tipo S>e solo se S e' l'assioma e non compare nella parte dx di nessuna regola....il motivo di questa limitazione non e' molto chiaro (e tra l'altro ho letto che questa domanda l'ha fatta) ma cmq le G2 e G3 invece contengono tranquillamente regole A>e, come mai? Non dovrebbero essere dei sottoinsiemi delle G1?

E inoltre pag. 27: esempio 2.2 non e' chiaro come riesce a dimostrare che per la G in esame una parola di lunghezza > 1 ammette esattamente un albero di derivazione....
esempio 2.3 (c'e' scritto 2.2 ma credo sia un errore): non riesco a trovare due alberi distinti per una parola del tipo a^ib^jc^j, anzi, se voglio b e c nella parola a non c'e' mai (devo partire con S>XC).

Posted by rdptz on 17-01-2004 18:04:

Originally posted by mozilla

Comunque per quello che vedo, riferendomi a voi 3 o 4 che state usando il forum, mi sembrate abbastanza preparati.

Beh, con davanti le dispense siamo preparati tutti :-) (casi disperati a parte)

Comunque sugli esempi non fatevi problemi, l'importante è che magari ne abbiate uno pronto per ogni tipo di linguaggio.

ok, grazie mille mi hai rassicurato :-)

Cmq se a qualcuno interessa (mi rendo conto che è un po' tardi) qui ci sono un po' di esercizi del tipo esempi di utilizzo del pumping lemma, data questa grammatica che tipo di L genera, etc.

http://cabibbo.dia.uniroma3.it/it/pdf_x2/

Posted by rdptz on 17-01-2004 19:53:

Originally posted by eugenio_2
Si' spero anch'io che non faccia domande di questo tipo o cmq si limiti a linguaggi "noti"....GNF CNF cosa intendi?

Greibach Normal Form, Chomsky Normal Form

A me e' venuto un dubbio madornale: le grammatiche di tipo 1 possono contenere regole di tipo S>e solo se S e' l'assioma e non compare nella parte dx di nessuna regola....il motivo di questa limitazione non e' molto chiaro (e tra l'altro ho letto che questa domanda l'ha fatta)

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

ma cmq le G2 e G3 invece contengono tranquillamente regole A>e, come mai? Non dovrebbero essere dei sottoinsiemi delle G1?

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

http://edenti.deis.unibo.it/Ling/20...Grammatiche.pdf

in pratica, secondo quella dispensa, la contraddizione c'è, ma è eliminabile
perchè in ogni G2 e G3 si può togliere la parola vuota e sostituirla con un'altra regola.

Perchè ci sia quella contraddizione non lo so. Cioè, non si faceva prima a evitare del tutto quel tipo di regola anche nelle G2 e G3?

non riesco a trovare due alberi distinti per una parola del tipo a^ib^jc^j, anzi, se voglio b e c nella parola a non c'e' mai (devo partire con S>XC).

io non ci ho nemmeno provato e non ci perderei tempo :-) Credo sia suff. sapere che quella è una G inerentemente ambigua.

Posted by rdptz on 17-01-2004 19:57:

Originally posted by rdptz

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

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.

Posted by xabry on 18-01-2004 10:02:

Originally posted by eugenio_2
Xabry tu dai l'esame martedi' 20?

Si io vado martedì e incrocio le dita!!!!

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

Originally posted by mozilla
Si

[B] Si, la parola la si ottiene semplicemente leggendo da sinistra a destra le foglie dell'albero, le quali contengono ciascuna un solo simbolo terminale.

In bocca al lupo, in culo alla balena, tra le palle del grillo e le tette della formica a TUTTI! (queste non le sapevate eh....!)

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?
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?
21) Equazioni e incognite?
--Ok le usa per Kleene ma che gli dico? Faccio esempio a pag. 24?

Grazie ancora Mozilla mi stai dando un aiuto gigantesco!!!

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