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

Pages (6): [1] 2 3 4 5 » ... Last »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- [Linguaggi Formali e Automi] Grammatiche (http://www.dsy.it/forum/showthread.php?threadid=7794)

Posted by ale82info on 06-01-2004 16:13:

Lfa

Qualcuno sa spiegarmi in parole povere la differenza tra i vari tipi di grammatiche!?
Grazie!

Posted by yoruno on 07-01-2004 07:22:

Re: Lfa

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

__________________
"Voi che tingete i mari del colore dello zinco, che tramutate i boschi in gialli deserti, i venti in fumi di polveri da sparo e che bruciate i cieli. Voi che volete ripetere i malvagi atti della sconsiderata Lilith, che fu la prima moglie di Adamo e poi la sposa del Diavolo. Voi che volete ripetere la ribellione scatenata da Lucifero, del mondo celeste il più splendente. Voi! Ascoltate l'afflizione della sottospecie alata che vola alta nel cielo." [Angel Sanctuary]
::: mail: yoruno@dsy.it ::: ::: My Site ::: ::: Dsy Photo Gallery ::: ::: DeviantART Gallery :::

Posted by maja on 07-01-2004 07:33:

Re: Re: Lfa

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

__________________
Non si dice ottimista,si dice illuso.
Non si dice pessimista,si dice realista.

Posted by yoruno on 07-01-2004 07:54:

Re: Re: Re: Lfa

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

Posted by mozilla on 09-01-2004 20:52:

Re: Lfa

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

__________________
"Direi che la signorina Lucy è più calorosa di una sposa di Giugno che cavalca nuda un cavallo senza sella in mezzo al Sahara" - Il Colono, Dracula di Francis Ford Coppola

Posted by eugenio_2 on 11-01-2004 14:57:

Re: Re: Lfa

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?

Posted by eugenio_2 on 11-01-2004 15:12:

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.

Posted by mozilla on 11-01-2004 15:57:

Re: Re: Re: Lfa

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.

__________________
"Direi che la signorina Lucy è più calorosa di una sposa di Giugno che cavalca nuda un cavallo senza sella in mezzo al Sahara" - Il Colono, Dracula di Francis Ford Coppola

Posted by mozilla on 11-01-2004 16:52:

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.

__________________
"Direi che la signorina Lucy è più calorosa di una sposa di Giugno che cavalca nuda un cavallo senza sella in mezzo al Sahara" - Il Colono, Dracula di Francis Ford Coppola

Posted by eugenio_2 on 12-01-2004 09:03:

Re: Re: Re: Re: Lfa

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.

Posted by mozilla on 12-01-2004 09:13:

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.

__________________
"Direi che la signorina Lucy è più calorosa di una sposa di Giugno che cavalca nuda un cavallo senza sella in mezzo al Sahara" - Il Colono, Dracula di Francis Ford Coppola

Posted by eugenio_2 on 12-01-2004 22:11:

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

Posted by mozilla on 13-01-2004 11:14:

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.

__________________
"Direi che la signorina Lucy è più calorosa di una sposa di Giugno che cavalca nuda un cavallo senza sella in mezzo al Sahara" - Il Colono, Dracula di Francis Ford Coppola

Posted by eugenio_2 on 13-01-2004 11:31:

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

Posted by mozilla on 13-01-2004 11:45:

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.

__________________
"Direi che la signorina Lucy è più calorosa di una sposa di Giugno che cavalca nuda un cavallo senza sella in mezzo al Sahara" - Il Colono, Dracula di Francis Ford Coppola

All times are GMT. The time now is 18:08.

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