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

Calendar

Members

Faq

Logout

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi G - M > Linguaggi formali e automi > [Linguaggi Formali e Automi] Grammatiche

Pages (6): « 1 2 [3] 4 5 6 »

Last Thread Next Thread

Author

Thread Expand all | Contract all

xabry

.illuminato.

User info:

Registered: Sep 2003
Posts: 179 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 2 Days, 0:48:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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:

17-01-2004 08:13

Click here to Send xabry a Private Message

mozilla

.precettore.

User info:

Registered: Jul 2003
Posts: 93 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:34:57 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

Last edited by mozilla on 17-01-2004 at 13:35

17-01-2004 12:19

Click here to Send mozilla a Private Message

eugenio_2

.primate.

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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".

17-01-2004 13:10

Click here to Send eugenio_2 a Private Message

eugenio_2

.primate.

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.

17-01-2004 13:21

eugenio_2

.primate.

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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?

17-01-2004 13:23

mozilla

.precettore.

User info:

Registered: Jul 2003
Posts: 93 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:34:57 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

Last edited by mozilla on 18-01-2004 at 13:18

17-01-2004 13:45

mozilla

.precettore.

User info:

Registered: Jul 2003
Posts: 93 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:34:57 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

17-01-2004 14:09

rdptz

.amico.

User info:

Registered: Apr 2003
Posts: 33 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: I fuori corso
Time Online: 6:42:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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"?

17-01-2004 14:22

Click here to Send rdptz a Private Message

mozilla

.precettore.

User info:

Registered: Jul 2003
Posts: 93 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:34:57 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

17-01-2004 17:13

eugenio_2

.primate.

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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).

17-01-2004 17:32

rdptz

.amico.

User info:

Registered: Apr 2003
Posts: 33 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: I fuori corso
Time Online: 6:42:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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/

17-01-2004 18:04

rdptz

.amico.

User info:

Registered: Apr 2003
Posts: 33 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: I fuori corso
Time Online: 6:42:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.

17-01-2004 19:53

rdptz

.amico.

User info:

Registered: Apr 2003
Posts: 33 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: I fuori corso
Time Online: 6:42:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.

17-01-2004 19:57

xabry

.illuminato.

User info:

Registered: Sep 2003
Posts: 179 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 2 Days, 0:48:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

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

18-01-2004 10:02

xabry

.illuminato.

User info:

Registered: Sep 2003
Posts: 179 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 2 Days, 0:48:11 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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!!!

18-01-2004 10:13

All times are GMT. The time now is 12:25.

Pages (6): « 1 2 [3] 4 5 6 »

Last Thread Next Thread

Show Printable Version |

Email this Page |

Subscribe to this Thread |

Add to Bookmarks

Forum Jump:

Rate This Thread:

Forum Rules:

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON

Pagina generata in 0.108 seconds (72.79% PHP - 27.21% MySQL) con 24 query.