.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 13-01-2004 14:48:

Originally posted by mozilla
Si è vero usa delta piccolo, però non usa il simbolo di uguale ma di equivalenza (o congruenza), quindi il delta di q e quello di q' portano in due stati che se non sono uguali sono comunque equivalenti.

Giusto!! Mi era sfuggito, davo per scontato che fosse un uguale, grazie!!

Originally posted by mozilla

Probabilmente per risolvere problemi di overloading di significato nei simboli di un linguaggio di alto livello come per l'uguale che hai citato tu, si usano quegli accrocchi che il prof. non ci aveva voluto spiegare pur rimanendo nei L acontestuali. O forse sono informazioni top secret che non ci vogliono dire.....!

Eh eh forse e' cosi'

Originally posted by mozilla
Ti vedo preparato, puoi puntare in alto

Sara', ma il pumping lemma mi sembra ancora una cosa incomprensibile

Posted by xabry on 13-01-2004 15:26:

Originally posted by mozilla
Si è vero usa delta piccolo, però non usa il simbolo di uguale ma di equivalenza (o congruenza), quindi il delta di q e quello di q' portano in due stati che se non sono uguali sono comunque equivalenti.

Probabilmente per risolvere problemi di overloading di significato nei simboli di un linguaggio di alto livello come per l'uguale che hai citato tu, si usano quegli accrocchi che il prof. non ci aveva voluto spiegare pur rimanendo nei L acontestuali. O forse sono informazioni top secret che non ci vogliono dire.....!

Ti vedo preparato, puoi puntare in alto
L'esame non è difficile, anche le assistenti sono molto oggettive nella valutazione e buone nelle domande.

Ciao ho letto le tue spiegazioni e ti ringrazio perchè hai chiarito un po' di cose anche a me. Ma volevo chiederti: per le dimostrazioni sono molto fiscali e rigorosi? Io avevo sentito che più che altro chiede esempi e concetti. E' così? Altrimenti mi sa che non ce la farò mai!!!!

Posted by mozilla on 13-01-2004 15:56:

Originally posted by xabry
Ciao ho letto le tue spiegazioni e ti ringrazio perchè hai chiarito un po' di cose anche a me. Ma volevo chiederti: per le dimostrazioni sono molto fiscali e rigorosi? Io avevo sentito che più che altro chiede esempi e concetti. E' così? Altrimenti mi sa che non ce la farò mai!!!!

No, purtroppo o per fortuna chiede le dimostrazioni. Purtroppo perchè studiarsi le dimostrazioni può essere un po' difficoltoso, almeno a ricordarsele; per fortuna perchè una volta che sai quelle penso che l'esame sia fatto! Ti faccio qualche esempio: a me ha chiesto la dimostrazione di inclusione dei linguaggi, che oltretutto è formata da 3 dimostrazioni, ma una volta spiattellate le prime due, la terza (quella dell'algoritmo di cui si parlava con eugenio_2) me l'ha appena fatta incominciare e poi mi ha mandato via; ad un mio amico ha chiesto la dimostrazione di Kleene, stessa storia, saputa quella è finito l'esame; una mia amica poi ha fatto il record, è stata seduta al massimo un paio di minuti, le ha chiesto una dimostrazione anche se non ricordo quale. Le dimostrazioni importanti da sapere poi, sono poche:
- dimostrazione di inclusione dei linguaggi
- teorema di Kleene
- pumping lemma
Non voglio dire di non studiare le altre, però queste sono quelle che è moooolto probabile che vi chieda

Oltretutto, visto che, al contrario di quanto pensavo, un certo documento è pubblico e pubblicato sul DSY, se non l'avete ancora scaricato, fatelo da QUI. :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 14-01-2004 08:51:

Originally posted by eugenio_2
Sara', ma il pumping lemma mi sembra ancora una cosa incomprensibile

Beh, non proprio incomprensibile

pero' rimane qualche dubbio es. perche' nella dimostrazione, riga 3 dice che l'albero di derivazione di z ha H foglie? Avendo z lunghezza > H le foglie saranno almeno H+1 no? 1 simbolo terminale = 1 foglia, o mi sbaglio?

Posted by freccia on 14-01-2004 14:41:

Devo sostenere l'appello a febbraio..
Per farlo con Bertoni è suffficiente studiare la sua dispensa di 32 pagine o c'è altro?

Grazie

Posted by freccia on 14-01-2004 14:47:

O bisogna studiare anche le dispense su XML?

Posted by eugenio_2 on 14-01-2004 15:13:

Originally posted by freccia
O bisogna studiare anche le dispense su XML?

E quale sarebbe?

Posted by giuliocap on 14-01-2004 16:27:

Mah......che io sappia......c'e' solo la sua dispensa....almeno....circa due o tre mesi fa, quando andai al ricevimento a chiedere informazioni sul programma, lui mi disse cosi'!
....e spero che nel frattempo le cose non siano cambiate!

Posted by freccia on 14-01-2004 16:49:

Mi era sorto il dubbio poichè quando ho scaricato la dispensa di Bertoni dal suo sito :

http://webcen.usr.dsi.unimi.it/2001.../lfa/index.html

c'era anche un'altra dispensa su XML e non avendo seguito il corso ero un pò in panico.

Probabilmente non serve.
Grazie

Posted by mozilla on 14-01-2004 17:53:

Originally posted by freccia
O bisogna studiare anche le dispense su XML?

No, c'è da studiare solo la sua dispensa. Su XML, l'anno scorso, è stato tenuto un seminario, forse è per quello che ci sono le dispense.

__________________
"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 freccia on 14-01-2004 23:21:

Per fortuna!
Mi hai tolto un bel dubbio!
grazie

Posted by xabry on 15-01-2004 08:09:

Originally posted by mozilla
No, purtroppo o per fortuna chiede le dimostrazioni. Purtroppo perchè studiarsi le dimostrazioni può essere un po' difficoltoso, almeno a ricordarsele; per fortuna perchè una volta che sai quelle penso che l'esame sia fatto! Ti faccio qualche esempio: a me ha chiesto la dimostrazione di inclusione dei linguaggi, che oltretutto è formata da 3 dimostrazioni, ma una volta spiattellate le prime due, la terza (quella dell'algoritmo di cui si parlava con eugenio_2) me l'ha appena fatta incominciare e poi mi ha mandato via; ad un mio amico ha chiesto la dimostrazione di Kleene, stessa storia, saputa quella è finito l'esame; una mia amica poi ha fatto il record, è stata seduta al massimo un paio di minuti, le ha chiesto una dimostrazione anche se non ricordo quale. Le dimostrazioni importanti da sapere poi, sono poche:
- dimostrazione di inclusione dei linguaggi
- teorema di Kleene
- pumping lemma
Non voglio dire di non studiare le altre, però queste sono quelle che è moooolto probabile che vi chieda

Oltretutto, visto che, al contrario di quanto pensavo, un certo documento è pubblico e pubblicato sul DSY, se non l'avete ancora scaricato, fatelo da QUI.

Ok sono più tranquilla adesso, però ho qualche domanda anche io.
Posso?
Ecco:

PAgina 10 Prop. 5.1

Non capisco come fa ad eliminare le regole del tipo A->B.
Mi fate un esempio?

Pagina 18 Prop. 4.1

Non ho ben capito il senso della Dim: costruisce una G di tipo 3 e
immagino voglia dimostrare che essa genera L(A) giusto?
Mi spiegate come lo fa?

Pagina 23 Teorema di Kleene (2) implica (1)

Anche qui ho dubbi sul senso della dim: dire che esiste un unica
soluzione al sistema signica che abbiamo trovato un espressione
regolare? E sarebbe la soluzione? E' così?

Pagina 24 Esempio 5.3

C'è un errore o sono tarda? Io mi aspettavo X0=ab*a+b=L
Sbaglio?

Pagina 28 Esempio 3.1

Che regola è A->( ,B->+, C-> ) ??????
Non capisco proprio che cavolo deriva?

Ultima domanda

Mi spegate in parole semplici o con un esempio il senso
del Pumping Lemma? Non riesco a trovare un esempio pratico

Spero mi aiutiate!!

Grazie

Posted by mozilla on 15-01-2004 15:31:

Originally posted by xabry
Ok sono più tranquilla adesso, però ho qualche domanda anche io.
Posso?
Ecco:

PAgina 10 Prop. 5.1

Non capisco come fa ad eliminare le regole del tipo A->B.
Mi fate un esempio?

Per eliminare queste regole bisogna effettuare quella che si chiama "chiusura transitiva del grafo" come nell'esempio seguente. Ammettiamo di avere le seguenti regole: A->B , B->A , B->C , A->aB , B->bC , C->a
le prime tre violano i linguaggi di tipo 3, quindi costruiamo un grafo che ha come nodi i metasimboli delle regole violate e come archi orientati le "frecce" delle regole di produzione violate, con in più i "cappi", ovvero ogni nodo produce se stesso, così:

<-----------|
(A)------->(B)------->(C)

I cappi non li ho segnati comunque ogni nodo ha una freccia che parte e rientra in se stesso.
Attraverso questo grafo possiamo scrivere, per ogni nodo, quale altro nodo produce in un numero arbitrario di passi, così:

Tabella 1:
1) A ==*==> A
2) A ==*==> B
3) A ==*==> C
4) B ==*==> A
5) B ==*==> B
6) B ==*==> C
7) C ==*==> C

Adesso ogni regola corretta, la riscrivo scambiando il metasimbolo alla sinistra della regola in tutti i modi possibili in cui è riscritto che risulta in Tabella 1, combinati con tutti i modi in cui posso riscrivere il metasimbolo alla destra della regola, così:

regola corretta: A->aB
A da cosa può derivare, o essere prodotto? In tabella 1, le produzioni 1 e 4 ci dicono che A può essere prodotto da A e da B.
B che cosa può produrre? Le produzioni 4,5,6 ci dicono che B riscrive (o produce) A,B,C.
Riscrivendo la regola con tutte le combinazioni, otteniamo:
A->aB
B->aB
A->aA
A->aB
A->aC
B->aA
B->aB
B->aC

Facendo lo stesso per la seconda regola corretta B->bC, otteniamo:
A->bC
B->bC
(ne abbiamo solo due perchè C riscrive solo se stesso, guarda grafo)

Ultima regola, C->a:
A->a
B->a
C->a
(qui non abbiamo metasimboli sulla destra)

Quindi tutte le regole della G equivalente sono quelle che abbiamo ottenuto, ovvero:
A->aB
B->aB
A->aA
A->aB
A->aC
B->aA
B->aB
B->aC
A->bC
B->bC
A->a
B->a
C->a

Pagina 18 Prop. 4.1
Non ho ben capito il senso della Dim: costruisce una G di tipo 3 e
immagino voglia dimostrare che essa genera L(A) giusto?
Mi spiegate come lo fa?

Questo è abbastanza semplice, prova a seguire bene le istruzioni 1,2,3,4 della dim. Gli stati sono i metasimboli, le etichette degli archi sono i simboli terminali, le frecce indicano la regola di produzione. Se hai un grafo:
(A)----a---->(B)
la regola sarà A->aB

Pagina 23 Teorema di Kleene (2) implica (1)
Anche qui ho dubbi sul senso della dim: dire che esiste un unica
soluzione al sistema signica che abbiamo trovato un espressione
regolare? E sarebbe la soluzione? E' così?

Trovare l'espressione regolare significa dimostrare la (2) implica (1), ovvero, se L è riconosciuto da un ASF allora L è denotato da una REG-EXPR.

Pagina 24 Esempio 5.3
C'è un errore o sono tarda? Io mi aspettavo X0=ab*a+b=L
Sbaglio?

Si hai ragione, non ho controllato bene però anch'io l'anno scorso avevo trovato l'errore e mi veniva leggermente diverso dal tuo: X0=(ab*a+b)*

Pagina 28 Esempio 3.1
Che regola è A->( ,B->+, C-> ) ??????
Non capisco proprio che cavolo deriva?

Le parentesi sono simboli terminali, non simboli sintattici delle regole di produzione

Ultima domanda
Mi spegate in parole semplici o con un esempio il senso
del Pumping Lemma? Non riesco a trovare un esempio pratico

Una volta che l'hai capito, avrai occasione di utilizzarlo nella dimostrazione dell'inclusione dei linguaggi, per dimostrare che R2 è incluso in R1.

: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 16-01-2004 16:48:

Complimente per l'ottima spiegazione, Mozilla.

A me invece e' venuto un dubbio sulla definizione di un ASF: pag. 12:
"se la parola w apparentenete a sigma*....delta_piccolo(q, w sigma_piccolo) e' lo stato in cui....."
ma perche' sigma_piccolo? Non basta w?

Al punto 2: non capisco perche' anche qua fa un esempio in cui l'automa riceve w e poi sigma_piccolo, non bastava sigma_piccolo? Poi secondo me inverte w con q, di solito si scrive delta_piccolo(q,w) giusto?

Posted by mozilla on 16-01-2004 20:03:

Originally posted by eugenio_2
Complimente per l'ottima spiegazione, Mozilla.

A me invece e' venuto un dubbio sulla definizione di un ASF: pag. 12:
"se la parola w apparentenete a sigma*....delta_piccolo(q, w sigma_piccolo) e' lo stato in cui....."
ma perche' sigma_piccolo? Non basta w?

Sono d'accordo con te, o basta w, oppure la riga sotto dovrebbe essere "...dopo aver ricevuto w+sigma_piccolo.".

Al punto 2: non capisco perche' anche qua fa un esempio in cui l'automa riceve w e poi sigma_piccolo, non bastava sigma_piccolo? Poi secondo me inverte w con q, di solito si scrive delta_piccolo(q,w) giusto?

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

__________________
"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 10:07.

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