Dsy Network www | forum | my | didattica | howto | wiki | el goog | stats | blog | dona | rappresentanti
Homepage
 Register   Calendar   Members  Faq   Search  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    Post New Thread    Post A Reply
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 è 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 :)

13-01-2004 14:48
Click Here to See the Profile for eugenio_2 Click here to Send eugenio_2 a Private Message Find more posts by eugenio_2 Add eugenio_2 to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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 è 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.....! :cool:

Ti vedo preparato, puoi puntare in alto :approved:
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!!!!

13-01-2004 15:26
Click Here to See the Profile for xabry Click Here to See the Blog of xabry Click here to Send xabry a Private Message Find more posts by xabry Add xabry to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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
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

13-01-2004 15:56
Click Here to See the Profile for mozilla Click here to Send mozilla a Private Message Find more posts by mozilla Add mozilla to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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 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?

14-01-2004 08:51
Click Here to See the Profile for eugenio_2 Click here to Send eugenio_2 a Private Message Find more posts by eugenio_2 Add eugenio_2 to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
freccia
dottor operatore ecologic

User info:
Registered: Oct 2003
Posts: 195 (0.03 al dì)
Location: Varese
Corso:
Anno: XXIII
Time Online: 7 Days, 1:43:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

Grazie

14-01-2004 14:41
Click Here to See the Profile for freccia Click Here to See the Blog of freccia Click here to Send freccia a Private Message Find more posts by freccia Add freccia to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
freccia
dottor operatore ecologic

User info:
Registered: Oct 2003
Posts: 195 (0.03 al dì)
Location: Varese
Corso:
Anno: XXIII
Time Online: 7 Days, 1:43:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

O bisogna studiare anche le dispense su XML?

14-01-2004 14:47
Click Here to See the Profile for freccia Click Here to See the Blog of freccia Click here to Send freccia a Private Message Find more posts by freccia Add freccia to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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 freccia
O bisogna studiare anche le dispense su XML?


E quale sarebbe?

14-01-2004 15:13
Click Here to See the Profile for eugenio_2 Click here to Send eugenio_2 a Private Message Find more posts by eugenio_2 Add eugenio_2 to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
giuliocap
.amico.

User info:
Registered: Feb 2003
Posts: 24 (0.00 al dì)
Location: Piombino
Corso: informatica
Anno: primo
Time Online: 3 Days, 6:50:50 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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!

14-01-2004 16:27
Click Here to See the Profile for giuliocap Click Here to See the Blog of giuliocap Click here to Send giuliocap a Private Message Find more posts by giuliocap Add giuliocap to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
freccia
dottor operatore ecologic

User info:
Registered: Oct 2003
Posts: 195 (0.03 al dì)
Location: Varese
Corso:
Anno: XXIII
Time Online: 7 Days, 1:43:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

14-01-2004 16:49
Click Here to See the Profile for freccia Click Here to See the Blog of freccia Click here to Send freccia a Private Message Find more posts by freccia Add freccia to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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 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

14-01-2004 17:53
Click Here to See the Profile for mozilla Click here to Send mozilla a Private Message Find more posts by mozilla Add mozilla to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
freccia
dottor operatore ecologic

User info:
Registered: Oct 2003
Posts: 195 (0.03 al dì)
Location: Varese
Corso:
Anno: XXIII
Time Online: 7 Days, 1:43:30 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Per fortuna!
Mi hai tolto un bel dubbio!
grazie

14-01-2004 23:21
Click Here to See the Profile for freccia Click Here to See the Blog of freccia Click here to Send freccia a Private Message Find more posts by freccia Add freccia to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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
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:



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

15-01-2004 08:09
Click Here to See the Profile for xabry Click Here to See the Blog of xabry Click here to Send xabry a Private Message Find more posts by xabry Add xabry to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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
Post

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

Last edited by mozilla on 15-01-2004 at 15:37

15-01-2004 15:31
Click Here to See the Profile for mozilla Click here to Send mozilla a Private Message Find more posts by mozilla Add mozilla to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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

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?

16-01-2004 16:48
Click Here to See the Profile for eugenio_2 Click here to Send eugenio_2 a Private Message Find more posts by eugenio_2 Add eugenio_2 to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
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
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

16-01-2004 20:03
Click Here to See the Profile for mozilla Click here to Send mozilla a Private Message Find more posts by mozilla Add mozilla to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
All times are GMT. The time now is 14:21.    Post New Thread    Post A Reply
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
 

Powered by: vBulletin v2.3.1 - Copyright ©2000 - 2002, Jelsoft Enterprises Limited
Mantained by dsy crew (email) | Collabora con noi | Segnalaci un bug | Archive | Regolamento | Licenze | Thanks | Syndacate
Pagina generata in 0.056 seconds (71.40% PHP - 28.60% MySQL) con 20 query.