 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[Linguaggi Formali e Automi] Grammatiche
Clicca QUI per vedere il messaggio nel forum |
| ale82info |
Qualcuno sa spiegarmi in parole povere la differenza tra i vari tipi di grammatiche!?
Grazie! |
| yoruno |
Originally posted by ale82info
Qualcuno sa spiegarmi in parole povere la differenza tra i vari tipi di grammatiche!?
Grazie!
Cosa sarebbe LFA?
Specificamelo, vorrei cambiare il nome del thread che non è assolutamente indicativo... |
| maja |
Originally posted by yoruno
Cosa sarebbe LFA?
Specificamelo, vorrei cambiare il nome del thread che non è assolutamente indicativo...
Linguaggi Formali e Automi,ma penso che la maggiorparte degli utenti lo conosca.... |
| yoruno |
Originally posted by maja
Linguaggi Formali e Automi,ma penso che la maggiorparte degli utenti lo conosca....
Ma io sono ancora col cervello in ferie :D |
| mozilla |
Originally posted by ale82info
Qualcuno sa spiegarmi in parole povere la differenza tra i vari tipi di grammatiche!?
Grazie!
Spero tu abbia le dispense delle lezioni per vedere più formalmente le differenze, comunque le grammatiche differiscono per i tipi di regole di produzione che ammettono. Conseguentemente ognuna genera linguaggi di una certa categoria, ovvero con una grammatica regolare che ha regole di produzione più "rigide" rispetto alle altre, non potrai generare tutti i tipi di linguaggi. Come esempio posso dirti che i linguaggi tradizionali procedurali come C, Pascal, etc. sono generati da grammatiche di tipo 2 (libere dal contesto). |
| eugenio_2 |
Originally posted by mozilla
Come esempio posso dirti che i linguaggi tradizionali procedurali come C, Pascal, etc. sono generati da grammatiche di tipo 2 (libere dal contesto).
Puoi spiegare meglio questa affermazione? Cosi' su due piedi pensavo fossero contestuali: es. il compilatore riconosce la parola "then" solo all'interno di un costrutto "if"....
Altri esempi su linguaggi realmenti esistenti? |
| eugenio_2 |
Approfitto di questo nuovo thread per esporre qualche dubbio.
1) Esempio 3.2 (pag. 8 dispense di Bertoni), la derivazione della parola parte con:
S-> a^(n-1)S(BC)^(n-1)
Perche' proprio n-1? C'e' qualche motivo particolare o semplicemente e' l'unico modo per derivare la parola?
2) Grammatiche di tipo 3: accettano regole del tipo A->sB, ma valgono anche quelle del tipo A->Bs ?
3) Proposizione 4.1 (pag. 9): dimostrazione: per dimostrare che ogni linguaggio R1 e' ricorsivo trova un algoritmo che riconosce le parole: ma quel tipo di algoritmo allora si potrebbe utilizzare anche con i linguaggi R0, eppure in R0 ci sono linguaggi non ricorsivi....
4) Proposizione 5.1 (pag. 10): dimostrazione: la trasformazione in grammatiche equivalenti porta ad una grammatica che contiene regole del tipo A->sB, A->s, A->e, A->B, sapreste farmi un esempio di una trasformazione che alla fine contenga regole A->B?
5) Proposizione 5.3 (pag. 11): dimostrazione: mi sembra che spieghi solo come ottenere L', non dimostra nulla, mi sbaglio?
6) Stati osservabili (pag. 13): uno stato e' osservabile se esiste una w per cui q=d(q0, w), ma quel q0 e' lo stato iniziale? Se si' lo stato deve essere osservabile in un passo a partire da q0 o anche in pi' passi?
Grazie e scusate la lunghezza. |
| mozilla |
Originally posted by eugenio_2
Puoi spiegare meglio questa affermazione? Cosi' su due piedi pensavo fossero contestuali: es. il compilatore riconosce la parola "then" solo all'interno di un costrutto "if"....
Altri esempi su linguaggi realmenti esistenti?
Mi hai fatto venire dei dubbi! :pensa:
In realtà non te lo so spiegare, ricordo che l'anno scorso a lezione aveva detto che i linguaggi classici procedurali che conosciamo sono di tipo 2 più l'aggiunta di qualcosa che non ci ha spiegato perchè non rientrava probabilmente nel programma e nelle nostre conoscenze.
Per altri esempi non posso essere molto più preciso: ricordo che Bertoni ci disse che linguaggi di basso livello appartengono (o possono appartenere) al tipo 3; forse l'assembler, o qualcosa di vecchio più vicino alla macchina di quanto lo siano comunque il C o Pascal.
XML intuitivamente mi viene da dire che sia un linguaggio regolare. Anche qui non ne sono sicuro purtroppo, so che è bilanciato (è facile verificarlo) e sicuramente in comune con i linguaggi di tipo 3 ha che è esprimibile con un espressione regolare.
Mi dispiace non essere stato molto preciso, è che durante il corso la parte nozionistica (e legata all'aspetto pratico) viene accantonata per studiare la teoria. Comunque potresti provare a chiedere direttamente a lui, è molto bravo a spiegare. |
| mozilla |
Originally posted by eugenio_2
Approfitto di questo nuovo thread per esporre qualche dubbio.
1) Esempio 3.2 (pag. 8 dispense di Bertoni), la derivazione della parola parte con:
S-> a^(n-1)S(BC)^(n-1)
Perche' proprio n-1? C'e' qualche motivo particolare o semplicemente e' l'unico modo per derivare la parola?
La scelta n-1 vuol dire che se tu vuoi ottenere la parola aaaabbbbcccc (quindi con n=4) devi applicare la prima regola per n-1 (cioè 3) volte ottenendo aaaSBCBCBC. Applicando le altre regole otterrai aaaabbbbcccc.
2) Grammatiche di tipo 3: accettano regole del tipo A->sB, ma valgono anche quelle del tipo A->Bs ?
NO.
In realtà (sempre se ricordo bene) la grammatica potrebbe essere equivalente se al posto che essere lineare a destra come quella regolare fosse lineare a sinistra cioè con regole A->Bs. Però sicuramente non puoi mischiare le regole altrimenti non sarebbe una G di tipo 3.
3) Proposizione 4.1 (pag. 9): dimostrazione: per dimostrare che ogni linguaggio R1 e' ricorsivo trova un algoritmo che riconosce le parole: ma quel tipo di algoritmo allora si potrebbe utilizzare anche con i linguaggi R0, eppure in R0 ci sono linguaggi non ricorsivi....
Sei sicuro di poter applicare quell'algoritmo per R0?Io ricordo di averlo fatto seguendo le spiegazioni e i conti tornavano.....
4) Proposizione 5.1 (pag. 10): dimostrazione: la trasformazione in grammatiche equivalenti porta ad una grammatica che contiene regole del tipo A->sB, A->s, A->e, A->B, sapreste farmi un esempio di una trasformazione che alla fine contenga regole A->B?
Mi sembra che le regole di tipo A->B debbano esserci dall'inizio per ritrovartele dopo la prima trasformazione, non penso che si possano generare da regole del tipo A->abcdB. Per esempio: A->B, B->A, B->C, A->abB, B->bcC, C->a
5) Proposizione 5.3 (pag. 11): dimostrazione: mi sembra che spieghi solo come ottenere L', non dimostra nulla, mi sbaglio?
si, ma spiegando come si ottiene L' di fatto dimostra che L=L' U {e}
6) Stati osservabili (pag. 13): uno stato e' osservabile se esiste una w per cui q=d(q0, w), ma quel q0 e' lo stato iniziale? Se si' lo stato deve essere osservabile in un passo a partire da q0 o anche in pi' passi?
q0 è lo stato iniziale. Uno stato si dice osservabile se è raggiungibile in un numero arbitrario di passi. E' una definizione più semplice a dirsi che non a scriverla formalmente(come sempre del resto!). Comunque il corso tratta solo automi osservabili, cioè senza stati in cui non si arriva mai. |
| eugenio_2 |
Originally posted by mozilla
XML intuitivamente mi viene da dire che sia un linguaggio regolare. Anche qui non ne sono sicuro purtroppo, so che è bilanciato (è facile verificarlo)
Ti ringrazio molto per le risposte (non ho ancora letto attentamente quelle all'altro mio post ma oggi lo faro'). Puoi spiegarmi cosa si intende per linguaggio bilanciato? (Non ho trovato nulla sulle dispense).
Grazie. |
| mozilla |
A lezione non l'avevamo fatto, ce lo ha spiegato a Tecnologie Web Sadegh quando abbiamo fatto l'XML. Praticamente è un linguaggio che ha simboli di apertura e simboli di chiusura. Come l'XML appunto, o come un qualsiasi linguaggio parentesizzato.
L'HTML invece, che non aderisce a regole rigide come l'XML, non è del tutto bilanciato. |
| eugenio_2 |
Originally posted by mozilla
Sei sicuro di poter applicare quell'algoritmo per R0?Io ricordo di averlo fatto seguendo le spiegazioni e i conti tornavano.....
Hai ragione, guardando meglio e' necessaria la regola l(b)>=l(a) e quindi siamo nell'ambito degli R1.
Mi sembra che le regole di tipo A->B debbano esserci dall'inizio per ritrovartele dopo la prima trasformazione, non penso che si possano generare da regole del tipo A->abcdB. Per esempio: A->B, B->A, B->C, A->abB, B->bcC, C->a
[/QUOTE]
Ah ok, se ci sono dall'inizio allora ci siamo.
Gia' che ci sono :)
pag 14: dimostrazione che se q e' equivalente a q' allora entrambi portano allo stesso stato, con in input la stessa parola (4). Alla fine della dim utilizza la funzione lambda, ok, i due q magari portano entrambi ad uno stato finale (e quindi le f() lambda hanno uno come risultato) ma gli stati potrebbero essere diversi (entrambi finali, ma diversi) no?
Teorema di Kleene: pag 23 il punto b in alto mi sembra un po' oscuro, potresti chiarirmi come si ottiene il contenuto di P2 (c'e' scritto P1 ma penso intenda P2).
Piu' sotto:
"Per ogni stato finale qk, possiamo quindi scrivere l'equazione":
.....
come si legge in modo discorsivo?
Grazie ancora!! |
| mozilla |
Originally posted by eugenio_2
pag 14: dimostrazione che se q e' equivalente a q' allora entrambi portano allo stesso stato, con in input la stessa parola (4). Alla fine della dim utilizza la funzione lambda, ok, i due q magari portano entrambi ad uno stato finale (e quindi le f() lambda hanno uno come risultato) ma gli stati potrebbero essere diversi (entrambi finali, ma diversi) no?
Si, infatti due stati sono equivalenti quando a fronte di uno stesso input portano non in uno stesso stato, ma in uno stesso tipo di stato, cioè finale o non finale.
Teorema di Kleene: pag 23 il punto b in alto mi sembra un po' oscuro, potresti chiarirmi come si ottiene il contenuto di P2 (c'e' scritto P1 ma penso intenda P2).
Si hai ragione non è P1 ma P2. Pensa la cosa come se l'unione di due automi sono gli automi in parallelo, ed il prodotto come i due automi in serie. Quindi per ottenere P2 devi eliminare tutte le regole q'->e che portano allo stato finale, e farle andare nel primo stato del secondo automa, quindi q'->S''. In questo modo hai creato l'automa "prodotto" che è i due automi di partenza messi in serie uno dopo l'altro.
Piu' sotto:
"Per ogni stato finale qk, possiamo quindi scrivere l'equazione":
.....
come si legge in modo discorsivo?
Sinceramente non ricordo, comunque l'unione tra l'insieme della parola vuota e l'altra roba è proprio un'unione, che in forma equazionale si trasforma in un '+'..... e forse anche quella all'interno della parentesi dovrebbe essere un'unione, quindi una sommatoria anche se in matematica siamo abituati a scriverla con una sigma grande... si, penso sia una sommatoria perchè poi quando costruisci l'equazione i 'sigma Xj' li sommi tra loro e l'eventuale epsilon.
:) |
| eugenio_2 |
Originally posted by mozilla
Si, infatti due stati sono equivalenti quando a fronte di uno stesso input portano non in uno stesso stato, ma in uno stesso tipo di stato, cioè finale o non finale.
Ma la proprieta' 4 (che e' quella che vuole dimostrare) dice che due stati equivalenti portano allo stesso q futuro (se guardi non usa lambda ma solo delta piccolo); il fatto che portino allo stesso tipo di stato non e' nemmeno da dimostrare IMHO perche' e' gia' insito nella definizione di stato indistinguibile/equivalente, giusto?
Originally posted by mozilla
Si hai ragione non è P1 ma P2. Pensa la cosa come se l'unione di due automi sono gli automi in parallelo, ed il prodotto come i due automi in serie. Quindi per ottenere P2 devi eliminare tutte le regole q'->e che portano allo stato finale, e farle andare nel primo stato del secondo automa, quindi q'->S''. In questo modo hai creato l'automa "prodotto" che è i due automi di partenza messi in serie uno dopo l'altro.
Ok, adesso e' molto piu' chiaro :)
Ho guardato un po' in Rete e in effetti i linguaggi di programmazione di alto livello sono considerati non contestuali, eppure ad es. ci sono simboli che in un contesto vogliono dire qualcosa e in un altro qualcos'altro (mi viene in mente il basic, in cui = sta sia per assegnazione che per comparazione).... |
| mozilla |
Originally posted by eugenio_2
Ma la proprieta' 4 (che e' quella che vuole dimostrare) dice che due stati equivalenti portano allo stesso q futuro (se guardi non usa lambda ma solo delta piccolo); il fatto che portino allo stesso tipo di stato non e' nemmeno da dimostrare IMHO perche' e' gia' insito nella definizione di stato indistinguibile/equivalente, giusto?
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.
:) |
| eugenio_2 |
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 :) |
| xabry |
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!!!! |
| mozilla |
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: |
| eugenio_2 |
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? |
| freccia |
Devo sostenere l'appello a febbraio..
Per farlo con Bertoni è suffficiente studiare la sua dispensa di 32 pagine o c'è altro?
Grazie |
| freccia |
| O bisogna studiare anche le dispense su XML? |
| eugenio_2 |
Originally posted by freccia
O bisogna studiare anche le dispense su XML?
E quale sarebbe? |
| giuliocap |
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! |
| freccia |
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 |
| mozilla |
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. |
| freccia |
Per fortuna!
Mi hai tolto un bel dubbio!
grazie |
| xabry |
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 |
| mozilla |
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: |
| 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?
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? |
| mozilla |
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).
:) |
| 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?
Ti ringrazio e "io speriamo che me la cavo"!!!!!
Ciao:sad: |
| mozilla |
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?
Si
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: |
| eugenio_2 |
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". |
| eugenio_2 |
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!:-D (queste non le sapevate eh....!)
:cool:
Crepi, grazie. :) |
| eugenio_2 |
Originally posted by xabry
Grazie Mozilla mi hai chiarito molte cose!
[....]
Ti ringrazio e "io speriamo che me la cavo"!!!!!
Ciao:sad:
Xabry tu dai l'esame martedi' 20? |
| mozilla |
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. |
| mozilla |
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? |
| rdptz |
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"? |
| mozilla |
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. |
| eugenio_2 |
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). |
| rdptz |
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/ |
| rdptz |
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. |
| rdptz |
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. |
| xabry |
Originally posted by eugenio_2
Xabry tu dai l'esame martedi' 20?
Si io vado martedì e incrocio le dita!!!!
:) |
| xabry |
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!:-D (queste non le sapevate eh....!)
:cool:
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!!! |
| eugenio_2 |
Originally posted by rdptz
Bella domanda: perchè quella limitazione impedisce alla frase di accorciarsi dopo una produzione.
Uhm, ma perche' dobbiamo impedire alla frase di accorciarsi? E' una proprieta' che va rispettata?
In generale per quanto riguarda la dimostrazione dell'inclusione tra i vari linguaggi, bisogna dimostrare solo che l'inclusione sia propria giusto? Il fatto che siano uno sottoinsieme (improprio) dell'altro e' gia' insito nelle proprieta' delle G, che hanno regole sempre piu' stringenti; e' corretto secondo voi?
E per quanto riguarda il riconoscimento dei linguaggi: gli ASF servono solo a riconoscere L3 o possono riconoscere anche degli L2: il caso a pag.30 non si capisce se e' un caso particolare oppure se gli ASF non possono riconoscere *nessun* L2.
Tra le domande ho visto anche questa:
"Esite espressione regolare che genera un linguaggio regolare?"
Ma tutti i L denotati da espressioni regolari sono regolari, o no? Se sono denotati da regexp allora c'e' un ASF che li riconosce, e quindi sono L3 (a meno che gli ASF non riconoscano anche gli L2 - vedi sopra - allora questa considerazione non vale).
Originally posted by rdptz
hai ragione. Questo secondo me il prof. doveva chiarirlo. Qui trovi una spiegazione
Ok, grazie mille. |
| eugenio_2 |
Originally posted by rdptz
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.
Ah ok, no non l'avevo assolutamente interpretata in senso ironico.
:) |
| eugenio_2 |
Originally posted by xabry
17) Esempio di G3 ambigua?
Questa mi era sfuggita....mi sembra che gli esempi che fatto sulle dispense siano tutti riferiti a G2, non saprei. |
| rdptz |
Originally posted by xabry
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?
credo la risposta giusta sia che non esiste una G3 ambigua, poichè le G3 sono le G generate da automi a stati finiti e un'automa a stati finiti non può essere ambiguo.
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?
credo proprio di sì.
21) Equazioni e incognite?
--Ok le usa per Kleene ma che gli dico? Faccio esempio a pag. 24?
piaerebbe saperlo anche a me. Io provo a guardare oggi quella parte, ch è quella più oscura (cioè non ho ben capito come passa da automa a regexp) |
| eugenio_2 |
Originally posted by xabry
Si io vado martedì e incrocio le dita!!!!
:)
Sai per caso in quanti siamo Martedi? |
| eugenio_2 |
Originally posted by rdptz
(cioè non ho ben capito come passa da automa a regexp)
Guarda il primo esempio e ti chiarisci le idee: un'equazione per ogni stato, un prodotto nella parte dx di ogni equazione per ogni simobolo terminale, composto dal simbolo terminare x lo stato che viene raggiunto con quel simbolo terminale.
Poi risolvi il sistema. |
| rdptz |
Originally posted by eugenio_2
Uhm, ma perche' dobbiamo impedire alla frase di accorciarsi? E' una proprieta' che va rispettata?
non lo so, non mi sembra che le dispense parlino mai di questa proprietà. Secondo me
ha a che fare con il funzionamento dei compilatori o con qualche parte di essi.
ma è solo un'ipotesi. Non ci ho riflettuto.
In generale per quanto riguarda la dimostrazione dell'inclusione tra i vari linguaggi, bisogna dimostrare solo che l'inclusione sia propria giusto?
sì, cioè la dimo. nelle dispense dimostra quello (poi è ovvio che essere sottoinsieme proprio implica l'essere anche sottoinsieme
improprio, nel senso che la prima è una proprietà più "stringente")
E per quanto riguarda il riconoscimento dei linguaggi: gli ASF servono solo a riconoscere L3 o possono riconoscere anche degli L2: il caso a pag.30 non si capisce se e' un caso particolare oppure se gli ASF non possono riconoscere *nessun* L2.
Fai attenzione che una G3 è anche una G2 quindi a rigore è sbagliato affermare che nessuna G2 può essere riconosciuta da un ASF.
Se invece ci si chiede: un ASF può riconoscere G2 che non sono anche G3?
Boh :-) Interessante. Secondo me no.
Si potrebbe provare a inventarsi una G con una regola tipo A->aBa e vedere se la B obbliga a mantenere memoria, cosa che un ASF non può fare.
Però da quel che ho capito (speriamo Mozillax non sia troppo ottimista :-) non è richiesta tutta questa riflessione sulla materia (che poi, certo, male non fa)
Sono questioni che si possono chiarire in sede d'esame. |
| ale82info |
| ma dall'appello di febbraio l'esame sarà scritto!? è vero o è una cazzata?! se non mi sbaglio sul sifa nella sezione dove si trovano gli appelli dei prox mesi! qualcuno sa qualcosa?! |
| mozilla |
Originally posted by xabry
17) Esempio di G3 ambigua?
Spontaneamente avrei detto anch'io che non esiste, ma sulle domande c'è già la risposta anche se non c'è un esempio. Sulle dispense oltretutto si dice chiaramente che una G3 ambigua esiste e che può essere trasformata nella equivalente G3 non ambigua. Un piccolissimo esempio potrebbe essere questo? A->aB , B->bC , B->b , C->epsilon
:?
Posso generare 'ab' in due modi diversi.....:pensa: |
| eugenio_2 |
Originally posted by rdptz
non lo so, non mi sembra che le dispense parlino mai di questa proprietà.
Ma tu l'hai letta da qualche parte?
Originally posted by rdptz
sì, cioè la dimo. nelle dispense dimostra quello (poi è ovvio che essere sottoinsieme proprio implica l'essere anche sottoinsieme
improprio, nel senso che la prima è una proprietà più "stringente")
In realta' la dim dimostra solo ad es. che In R2 ci sono linguaggi che non ci sono in R3, e questo, *se R3 è un sottoinsieme di R2* (ma questo non viene mai provato se non indirettamente enunciando le regole di produzione delle varie G), dimostra che è un sottoinsieme proprio.
Originally posted by rdptz
Fai attenzione che una G3 è anche una G2 quindi a rigore è sbagliato affermare che nessuna G2 può essere riconosciuta da un ASF.
Se invece ci si chiede: un ASF può riconoscere G2 che non sono anche G3?
Boh :-) Interessante. Secondo me no
[....].
Si' la tua puntualizzazione e' corretta non ho esplicitato tutto il concetto perche' ero di fretta :) ma in questa materia mi sa che bisogna essere molto formali.
Se tu domani vai e se hai tempo/voglia al tuo ritorno puoi fare un resoconto qua? (Se c'e' stato l'esame, come e' andato, se Martedi' c'e' Bertoni....). |
| rdptz |
Originally posted by eugenio_2
Ma tu l'hai letta da qualche parte?
La deduco dalle regole. Come fai ad accorciare una parola se a destra non hai mai metasimboli che "si annullano"?
E' impossibile che una produzione di Ab o di bA sia meno lunga di 2.
Se A fosse l'assioma potresti avere una regola A->e ma questa viene detto che è accettata solo se A non compare a dx di nessuna espressione (in sostanza
A->e serve solo a creare la parola vuota, non ha altre applicazioni nelle G1)
In realta' la dim dimostra solo ad es. che In R2 ci sono linguaggi che non ci sono in R3, e questo, *se R3 è un sottoinsieme di R2* (ma questo non viene mai provato se non indirettamente enunciando le regole di produzione delle varie G), dimostra che è un sottoinsieme proprio.
Sì in effetti mi sa che hai ragione e che è più corretto vederla così. Dimostro che sono sottoinsiemi propri e parto dall'assunto che siano sottoinsiemi (assunto, che è evidente di per sè guardando le regole: "chiaramente le G di tipo K sono un sottinsieme ... ")
Se tu domani vai e se hai tempo/voglia al tuo ritorno puoi fare un resoconto qua? (Se c'e' stato l'esame, come e' andato, se Martedi' c'e' Bertoni....).
sì sì, io vado salvo catastrofi. Vi faccio sapere. |
| xabry |
Originally posted by eugenio_2
[BIn generale per quanto riguarda la dimostrazione dell'inclusione tra i vari linguaggi, bisogna dimostrare solo che l'inclusione sia propria giusto? Il fatto che siano uno sottoinsieme (improprio) dell'altro e' gia' insito nelle proprieta' delle G, che hanno regole sempre piu' stringenti; e' corretto secondo voi?[/B]
Si secondo me si anche perchè altrimenti non basterebbe dim. per un linguaggio preciso ma dovrebbe dimostrarlo in modo generale per tutti! |
| xabry |
Originally posted by eugenio_2
Sai per caso in quanti siamo Martedi?
Non ne ho idea! |
| eugenio_2 |
| Qualcuno sa come si svolgono operativamente gli esami di Bertoni: fa un appello prima? L'ordine lo decide lui? E' un problema se si arriva in ritardo (i treni non sempre sono puntuali :) )? |
| mozilla |
Originally posted by eugenio_2
Qualcuno sa come si svolgono operativamente gli esami di Bertoni: fa un appello prima? L'ordine lo decide lui? E' un problema se si arriva in ritardo (i treni non sempre sono puntuali :) )? L'anno scorso aveva preso i nomi, il primo che glielo diceva lui lo scriveva. Aveva dovuto dividerci in più gruppi perchè eravamo tanti, il giorno dell'esame non ricordo se rifà l'appello, però da la precedenza a quelli che hanno esigenze particolari. In generale è molto tranquillo, quindi anche se dovessi arrivare in ritardo non penso che si infervori:swear:
Un consiglio, non mettete magliette con scritto E=mc^2 : lui è un fisico, vi chiederebbe di discuterla! :-D |
| rdptz |
Eccomi, stamattina sono passato ma c'era solo un altro ragazzo.
Visto che non c'era nessuno ce ne siamo andati dopo un po'.
Poi mentre andavamo via mi ha detto che ha visto arrivare la Palumbo - io non la conosco - ma a quel punto ho preferito rimandare perchè mi ha anche detto che lei fa l'esame basandosi sulle dispense di Goldwurm, e ho preferito non rischiare.
Quindi, a domani. |
| eugenio_2 |
Originally posted by mozilla
L'anno scorso aveva preso i nomi, il primo che glielo diceva lui lo scriveva. Aveva dovuto dividerci in più gruppi perchè eravamo tanti, il giorno dell'esame non ricordo se rifà l'appello, però da la precedenza a quelli che hanno esigenze particolari. In generale è molto tranquillo, quindi anche se dovessi arrivare in ritardo non penso che si infervori:swear:
Un consiglio, non mettete magliette con scritto E=mc^2 : lui è un fisico, vi chiederebbe di discuterla! :-D
Ok, grazie. |
| eugenio_2 |
Originally posted by rdptz
Eccomi, stamattina sono passato ma c'era solo un altro ragazzo.
Visto che non c'era nessuno ce ne siamo andati dopo un po'.
Poi mentre andavamo via mi ha detto che ha visto arrivare la Palumbo - io non la conosco - ma a quel punto ho preferito rimandare perchè mi ha anche detto che lei fa l'esame basandosi sulle dispense di Goldwurm, e ho preferito non rischiare.
Quindi, a domani.
Ok, grazie per il resoconto. |
| eugenio_2 |
E' andata, c'erano la Palano e un'altra ragazza, mi ha interrogato la Palano e mi ha dato 30.
Devo dire che le domande non sono state facilissime, pero' visto il risultato non mi lamento :)
Volevo ringraziare tutti e in particolare Mozilla che mi ha aiutato a risolvere gli ultimi dubbi, grazie mille!! |
| Simpsons |
Molte domande ti ha fatto Eugenio_2?
Su quali argomenti?
Quindi meglio la Palano o Bertoni? |
| mozilla |
Originally posted by eugenio_2
E' andata, c'erano la Palano e un'altra ragazza, mi ha interrogato la Palano e mi ha dato 30.
Devo dire che le domande non sono state facilissime, pero' visto il risultato non mi lamento :)
Volevo ringraziare tutti e in particolare Mozilla che mi ha aiutato a risolvere gli ultimi dubbi, grazie mille!!
Grande!:approved: :approved: :approved: |
| xabry |
Anche a me è andata!! Io ho preso 28! Devo dire che però l'assistente era molto tranquilla. Io ho avuto un paio di imperfezioni per il resto sono andata molto bene.
Mi ha chiesto
-espressioni regolari
-Teorema di Kleene
-Forme normali
-Automa a pila
Son contenta per Eugenio per la parte che ho visto io è stato torchiato ben bene ma ha tenuto testa!!!
Bravo!!
Ciao:)
E un grazie speciale a Mozilla senza di te non ce l'avrei fatta!!! |
| mozilla |
Originally posted by xabry
E un grazie speciale a Mozilla senza di te non ce l'avrei fatta!!! Grazie a voi per avermi fatto ripassare Linguaggi! Sarebbe caduta nel dimenticatoio.
Complimenti a tutti e due :approved: (ve l'avevo detto che eravate preparati ;) )
:cool: |
| Morgana |
Originally posted by xabry
Direi di si, ma a me sono stati utili anche gli esercizi (gli esempi chiariscono le formule spesso astratte e generali). Guarda bene qui
http://cabibbo.dia.uniroma3.it/it/pdf_x2/
Grazie mille! |
| eugenio_2 |
Originally posted by xabry
Anche a me è andata!! Io ho preso 28! Devo dire che però l'assistente era molto tranquilla. Io ho avuto un paio di imperfezioni per il resto sono andata molto bene.
Mi ha chiesto
-espressioni regolari
-Teorema di Kleene
-Forme normali
-Automa a pila
Son contenta per Eugenio per la parte che ho visto io è stato torchiato ben bene ma ha tenuto testa!!!
Bravo!!
Grazie e i miei complimenti a te :)
Non ho invece visto/riconosciuto rdptz; rdptz hai dato l'esame? |
| eugenio_2 |
Originally posted by Simpsons
Molte domande ti ha fatto Eugenio_2?
Su quali argomenti?
Dunque l'interrogazione non e' stata cortissima ma neanche lunga: se non ricordo male almeno 15-20 minuti (giusto xabri?).
E' partita chiedendomi di definire una grammatica e di spiegare la classificazione di Chomsky, mi ha poi chiesto di spiegare perche' una grammatica puo' essere considerata un sistema generativo, quindi ho dovuto spiegare cos'e' un sistema generativo (con la parte sulla relazione V(w,d) con proprieta' di correttezza, completezza etc. la procedura che non termina se non esiste un d tale che V(w,d)=1 etc etc), poi chiarire che una G e' un sistema generativo perche' e' possibile trovare qualcosa che rappresenta d (vedi dispense).
Mi ha poi chiesto di spiegare il rapporto tra G3 e automi, quindi ho spiegato cosa sono gli ASF; e dopo di definire un linguaggio, inventandolo (che non fosse finito o unario, tipo a^2n non andava bene) e di specificare la G che lo genera e poi di costruire l'ASF relativo....probabilmente mi ha anche chiesto altre cose che ora non ricordo :)
Diciamo che e' stata puntigliosa (tipo io avevo definito subito la funzione delta_piccolo(q,w), dopo aver detto che e' una funzione da SxQ a Q, in realta' dovevo definirla delta_piccolo(q,sigma_piccolo) e poi per induzione (q,Wsigma_piccolo) etc etc.) pero' del resto e' anche la materia che lo richiede. |
| rdptz |
Originally posted by eugenio_2
Grazie e i miei complimenti a te :)
Non ho invece visto/riconosciuto rdptz; rdptz hai dato l'esame?
Ero in prima fila, capelli corti e occhiali, e mi sono fatto spostare a venerdì. Avevo l'orale di Statistica ieri e lunedì ero un po' teso e deconcentrato.
Quindi domani è il mio turno. Speriamo :-)
Complimenti per l'esame, ti assicuro che dall'esterno mi sembrava non finisse più, ti ha chiesto di tutto e mi è sembrata molto pignola.
Xabry, tu sei la ragazza mora con i vari moduli per il trasferimento? Caspita meritavi 30 anche tu, sul serio. Non hai perso un colpo. Ci sono rimasto quando ti ha detto 28! |
| xabry |
Originally posted by rdptz
Ero in prima fila, capelli corti e occhiali, e mi sono fatto spostare a venerdì. Avevo l'orale di Statistica ieri e lunedì ero un po' teso e deconcentrato.
Quindi domani è il mio turno. Speriamo :-)
Complimenti per l'esame, ti assicuro che dall'esterno mi sembrava non finisse più, ti ha chiesto di tutto e mi è sembrata molto pignola.
Xabry, tu sei la ragazza mora con i vari moduli per il trasferimento? Caspita meritavi 30 anche tu, sul serio. Non hai perso un colpo. Ci sono rimasto quando ti ha detto 28!
Si sono io e credo che il 28 fosse per qualche sbavatura, che ti devo dire!! Cmq va bene così, sono contenta di averlo passato perchè non è che mi fosse proprio simpatico!!! Decisamente preferisco ora studiare Reti!!!
Ciao! |
| Simpsons |
Originally posted by eugenio_2
Dunque l'interrogazione non e' stata cortissima ma neanche lunga: se non ricordo male almeno 15-20 minuti (giusto xabri?).
E' partita chiedendomi di definire una grammatica e di spiegare la classificazione di Chomsky, mi ha poi chiesto di spiegare perche' una grammatica puo' essere considerata un sistema generativo, quindi ho dovuto spiegare cos'e' un sistema generativo (con la parte sulla relazione V(w,d) con proprieta' di correttezza, completezza etc. la procedura che non termina se non esiste un d tale che V(w,d)=1 etc etc), poi chiarire che una G e' un sistema generativo perche' e' possibile trovare qualcosa che rappresenta d (vedi dispense).
Mi ha poi chiesto di spiegare il rapporto tra G3 e automi, quindi ho spiegato cosa sono gli ASF; e dopo di definire un linguaggio, inventandolo (che non fosse finito o unario, tipo a^2n non andava bene) e di specificare la G che lo genera e poi di costruire l'ASF relativo....probabilmente mi ha anche chiesto altre cose che ora non ricordo :)
Diciamo che e' stata puntigliosa (tipo io avevo definito subito la funzione delta_piccolo(q,w), dopo aver detto che e' una funzione da SxQ a Q, in realta' dovevo definirla delta_piccolo(q,sigma_piccolo) e poi per induzione (q,Wsigma_piccolo) etc etc.) pero' del resto e' anche la materia che lo richiede.
Ok grazie mille! |
| eugenio_2 |
Originally posted by rdptz
Ero in prima fila, capelli corti e occhiali, e mi sono fatto spostare a venerdì.
Andando per esclusione avevo immaginato.
Originally posted by rdptz
Quindi domani è il mio turno. Speriamo :-)
In bocca al lupo allora :) |
| rdptz |
Originally posted by eugenio_2
Andando per esclusione avevo immaginato.
io ho capito dopo che eri tu, mi spiace non essermi fatto riconoscere ma ero un po' teso per l'esame di statistica
In bocca al lupo allora :)
Fatto. Sono un po' deluso, ho preso 27 ma non ho capito dove ho perso quei 3 punti.
Mi ha interrogato l'assistente che ha interrogato anche xabry. Argomento a piacere e sono partito con gli automi. Stavo andando spedito (automi, g3, da g3 ad automa, da automa a g3, da automi non deterministico a automa deterministico). Forse ho avuto qualche imprecisione formale nell'esposizione ma i concetti erano chiari e non ho avuto mai bisogno di imbeccate.
A un certo punto mi ha bloccato e mi ha proposto un 25.
Ha visto la mia faccia delusa e mi ha chiesto se volevo altre domande. Le ho risposto di sì ed è arrivato anche Bertoni.
Bertoni mi ha chiesto gli automi a pila con l'esempio passo passo, poi mi ha chiesto vari collegamenti (esempi di utilizzo degli automi in informatica) e sono andato bene.
Alla fine Bertoni ha detto che per lui andava bene, che ero sicuro e in grado di fare i collegamenti, l'assistente ha detto che anche sulla sua parte avevo mostrato di avere le idee chiare. Bertoni però voleva che fosse lei a decidere il voto e così lei ha deciso :-( IMHO è un po' tirchia nella valutazione.
Peccato perchè non credo avrei potuto far di meglio, ma capita. Magari non meritavo di passare in statistica. Alla fine credo che tutto si bilanci.
Va beh, mantengo la media ed è quasi finita. Mi mancano solo i complementari :-)
Buon proseguimento e grazie a tutti per il piacevole scambio di opinioni sul corso. |
| eugenio_2 |
Originally posted by rdptz
io ho capito dopo che eri tu, mi spiace non essermi fatto riconoscere ma ero un po' teso per l'esame di statistica
Don't worry anch'io stavo pensando al mio esame :)
Originally posted by rdptz
Fatto. Sono un po' deluso, ho preso 27 ma non ho capito dove ho perso quei 3 punti.
Mi ha interrogato l'assistente che ha interrogato anche xabry.
[....]
Mi dispiace, se meritavi di piu' era giusto che lo avessi, ma complimenti perche' e' cmq un ottimo voto!!
Originally posted by rdptz
Buon proseguimento e grazie a tutti per il piacevole scambio di opinioni sul corso.
Grazie a te.
Ciao. |
| xabry |
Originally posted by rdptz
io ho capito dopo che eri tu, mi spiace non essermi fatto riconoscere ma ero un po' teso per l'esame di statistica
Fatto. Sono un po' deluso, ho preso 27 ma non ho capito dove ho perso quei 3 punti.
Mi ha interrogato l'assistente che ha interrogato anche xabry. Argomento a piacere e sono partito con gli automi. Stavo andando spedito (automi, g3, da g3 ad automa, da automa a g3, da automi non deterministico a automa deterministico). Forse ho avuto qualche imprecisione formale nell'esposizione ma i concetti erano chiari e non ho avuto mai bisogno di imbeccate.
A un certo punto mi ha bloccato e mi ha proposto un 25.
Ha visto la mia faccia delusa e mi ha chiesto se volevo altre domande. Le ho risposto di sì ed è arrivato anche Bertoni.
Bertoni mi ha chiesto gli automi a pila con l'esempio passo passo, poi mi ha chiesto vari collegamenti (esempi di utilizzo degli automi in informatica) e sono andato bene.
Alla fine Bertoni ha detto che per lui andava bene, che ero sicuro e in grado di fare i collegamenti, l'assistente ha detto che anche sulla sua parte avevo mostrato di avere le idee chiare. Bertoni però voleva che fosse lei a decidere il voto e così lei ha deciso :-( IMHO è un po' tirchia nella valutazione.
Peccato perchè non credo avrei potuto far di meglio, ma capita. Magari non meritavo di passare in statistica. Alla fine credo che tutto si bilanci.
Va beh, mantengo la media ed è quasi finita. Mi mancano solo i complementari :-)
Buon proseguimento e grazie a tutti per il piacevole scambio di opinioni sul corso.
Sai mi sa che la tipa è buona ma tirchia!!! E vabbè dai l'importante è che lo abbiamo superato!! A me ora tocca Reti e poi ho finito.
Buon proseguimento anche a te |
| freccia |
Mi sono iscitto all'esame di febbraio.
Possibile che è scritto e non più orale?? |
| eugenio_2 |
Originally posted by freccia
Mi sono iscitto all'esame di febbraio.
Possibile che è scritto e non più orale??
Se non ricordo male anche quando l'ho dato io sul sifa risultava scritto invece era orale. |
| rdptz |
Originally posted by eugenio_2
Se non ricordo male anche quando l'ho dato io sul sifa risultava scritto invece era orale.
Sì ricordi bene :-)
Stiamo parlando dello scorso appello. Ai tempi ero andato a chiedere chiarimenti a Bertoni e ho avuto l'impressione che non ne sapesse nulla (cioè che fosse un'imprecisione del sifa). |
| xabry |
Originally posted by eugenio_2
Se non ricordo male anche quando l'ho dato io sul sifa risultava scritto invece era orale.
Confermo c'ero anche io!!!:) |
| freccia |
| Perfetto! grazie a tutti per l'interessamento! |
| freccia |
Qualcuno sa a che ora è l'esame martedì 17? Sempre che non cambiano data all'ultimo momento..
Grazie! |
|
|
|
|
