|
.primate.
Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline
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 |
|
|
| |
|
.illuminato.
Registered: Sep 2003
Posts: 179 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 2 Days, 0:48:11 [...]
Status: Offline
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.....!
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!!!!
|
13-01-2004 15:26 |
|
|
| |
|
.precettore.
Registered: Jul 2003
Posts: 93 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:34:57 [...]
Status: Offline
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.
__________________
"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 |
|
|
| |
|
.primate.
Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline
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 |
|
|
| |
|
dottor operatore ecologic
Registered: Oct 2003
Posts: 195 (0.03 al dì)
Location: Varese
Corso:
Anno: XXIII
Time Online: 7 Days, 1:43:30 [...]
Status: Offline
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 |
|
|
| |
|
dottor operatore ecologic
Registered: Oct 2003
Posts: 195 (0.03 al dì)
Location: Varese
Corso:
Anno: XXIII
Time Online: 7 Days, 1:43:30 [...]
Status: Offline
Edit | Report | IP: Logged |
O bisogna studiare anche le dispense su XML?
|
14-01-2004 14:47 |
|
|
| |
|
.primate.
Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by freccia
O bisogna studiare anche le dispense su XML?
E quale sarebbe?
|
14-01-2004 15:13 |
|
|
| |
|
.amico.
Registered: Feb 2003
Posts: 24 (0.00 al dì)
Location: Piombino
Corso: informatica
Anno: primo
Time Online: 3 Days, 6:50:50 [...]
Status: Offline
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 |
|
|
| |
|
dottor operatore ecologic
Registered: Oct 2003
Posts: 195 (0.03 al dì)
Location: Varese
Corso:
Anno: XXIII
Time Online: 7 Days, 1:43:30 [...]
Status: Offline
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 |
|
|
| |
|
.precettore.
Registered: Jul 2003
Posts: 93 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:34:57 [...]
Status: Offline
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 |
|
|
| |
|
dottor operatore ecologic
Registered: Oct 2003
Posts: 195 (0.03 al dì)
Location: Varese
Corso:
Anno: XXIII
Time Online: 7 Days, 1:43:30 [...]
Status: Offline
Edit | Report | IP: Logged |
Per fortuna!
Mi hai tolto un bel dubbio!
grazie
|
14-01-2004 23:21 |
|
|
| |
|
.illuminato.
Registered: Sep 2003
Posts: 179 (0.02 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 2 Days, 0:48:11 [...]
Status: Offline
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.
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 |
|
|
| |
|
.precettore.
Registered: Jul 2003
Posts: 93 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:34:57 [...]
Status: Offline
Edit | Report | IP: Logged |
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.
__________________
"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 |
|
|
| |
|
.primate.
Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline
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 |
|
|
| |
|
.precettore.
Registered: Jul 2003
Posts: 93 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 23:34:57 [...]
Status: Offline
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 |
|
|
| |
|
All times are GMT. The time now is 14:21. |
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|