 |
 alelorenz |
| esempi di chomsky |
12-07-2008 14:04 |
|
 |
alelorenz |
.fedelissimo.
Registered: Oct 2006
Posts: 53 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 18:21:12 [...]
Status: Offline
Edit | Report | IP: Logged |
esempi di chomsky
ciao... qualcuno riesce a farmi 4 veloci esempi di linguaggi da grammatiche di chomsky???
|
|
12-07-2008 14:04 |
|
|
| |
|
| Nothingsoul |
| Re: esempi di chomsky |
28-09-2008 12:44 |
|
|
Nothingsoul |
.simpatizzante.
Registered: Aug 2007
Posts: 13 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 2 Days, 10:59:22 [...]
Status: Offline
Edit | Report | IP: Logged |
Re: esempi di chomsky
Originally posted by alelorenz
ciao... qualcuno riesce a farmi 4 veloci esempi di linguaggi da grammatiche di chomsky???
Tipo 3: L={a^2n | n>0}
Come si può facilmente verificare, L è producibile a partire dalla grammatica G={(a), (S,A), (S->Aa, A->aS, A->a), S}. Inoltre esiste sicuramente un FSA che riconosce L, in quanto il relativo automa minimo ha un numero finito di stati. Dunque L è sicuramente di tipo 3.
Altri esempi:
le grammatiche G={(S), (a,b), (S->aS, S->b), S} e G'={(k,y,h), (S,A), (S->kS, S->yA, S->y, A->hA, A->h), S } generano linguaggi di tipo 3.
Tipo 2: L={a^n b^n | n>0}
L è producibile a partire da una grammatica G con regole S->aSb, S->ab. Tale grammatica rispetta tutte le restrizioni imposte dalla gerarchia di Chomsky per le grammatiche di tipo 2. Inoltre L non è sicuramente di tipo 3, in quanto se esiste un FSA in grado di riconoscere L, il rispettivo automa minimo ha infiniti stati (assurdo). Si può anche notare che G è lineare sia a destra che a sinistra.
Altri esempi:
i linguaggi L={a^h b^k c^(h+k) | h,k>0} e L'={a^n b^m c^j | n,m,j>0} sono context free, in quanto verificano il Pumping Lemma. In alternativa, si può sottolineare che esistono due grammatiche di tipo 2 in grado di generare L ed L'.
Tipo 1: L={a^n b^n c^n | n>1}
La grammatica G che genera L è lineare sia a destra che a sinistra. Inoltre ammette regole del tipo kA->kh, AB->BA, che violano le restrizioni imposte dalla classificazione di Chomsky per le grammatiche di tipo 2 e 3. Tuttavia, le regole di produzione di G sono tali che la lunghezza di ogni stringa derivata è sempre maggiore della lunghezza della stringa di origine. Considerando il fatto che L è chiaramente context-sensitive, si può concludere che L è di tipo 1.
Altri esempi:
L={a^n b^n c^n d^n | n>0} è context-sensitive.
Tipo 0: Un qualsiasi linguaggio ricorsivamente numerabile, senza particolari restrizioni sulle regole di produzione.
Last edited by Nothingsoul on 28-09-2008 at 12:51
|
|
28-09-2008 12:44 |
|
|
| |
|
| saradid |
| ciao scusate ma in modo pratico come si traducono ... |
04-06-2009 15:52 |
|
|
saradid |
.grande:maestro.
Registered: Aug 2003
Posts: 753 (0.10 al dì)
Location:
Corso: Informatica Serale
Anno: 2
Time Online: 27 Days, 15:44:06: [...]
Status: Offline
Edit | Report | IP: Logged |
ciao scusate ma in modo pratico come si traducono gli esempi sopra?
********
Tipo 3: L={a^2n | n>0}
Come si può facilmente verificare, L è producibile a partire dalla grammatica G={(a), (S,A), (S->Aa, A->aS, A->a), S}.
in che senso?
|
|
04-06-2009 15:52 |
|
|
| |
|
| saradid |
| qualcuno mi puo' aiutare? grazie ... |
10-06-2009 14:09 |
|
|
saradid |
.grande:maestro.
Registered: Aug 2003
Posts: 753 (0.10 al dì)
Location:
Corso: Informatica Serale
Anno: 2
Time Online: 27 Days, 15:44:06: [...]
Status: Offline
Edit | Report | IP: Logged |
qualcuno mi puo' aiutare? grazie
|
|
10-06-2009 14:09 |
|
|
| |
|
| dieguito |
| [QUOTE][i]Originally posted by saradid [/i]
... |
11-06-2009 12:51 |
|
|
dieguito |
.precettore.
Registered: Dec 2006
Posts: 85 (0.01 al dì)
Location: Milano
Corso: Informatica
Anno: secondo...più o meno..
Time Online: 1 Day, 10:36:09: [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by saradid
ciao scusate ma in modo pratico come si traducono gli esempi sopra?
********
Tipo 3: L={a^2n | n>0}
Come si può facilmente verificare, L è producibile a partire dalla grammatica G={(a), (S,A), (S->Aa, A->aS, A->a), S}.
in che senso?
stesso identico dubbio... mi accodo anch'io alla richiesta...
|
|
11-06-2009 12:51 |
|
|
| |
|
| saradid |
| speriamo che qualcuno ci illumini...senza esempi p ... |
11-06-2009 13:17 |
|
|
saradid |
.grande:maestro.
Registered: Aug 2003
Posts: 753 (0.10 al dì)
Location:
Corso: Informatica Serale
Anno: 2
Time Online: 27 Days, 15:44:06: [...]
Status: Offline
Edit | Report | IP: Logged |
speriamo che qualcuno ci illumini...senza esempi pratici questo esame non si capisce tanto...
|
|
11-06-2009 13:17 |
|
|
| |
|
| lSical |
| Ciao, la prof a lezione aveva fatto quel esempio p ... |
11-06-2009 14:51 |
|
|
lSical |
.consigliere.
Registered: Mar 2008
Posts: 102 (0.02 al dì)
Location:
Corso: Informatica
Anno: 1
Time Online: 5 Days, 1:00:41 [...]
Status: Offline
Edit | Report | IP: Logged |
Ciao, la prof a lezione aveva fatto quel esempio però con regole diverse:
G per {a^2n | n>0} V={S}
S->aa
S->aaS
in pratica è di tipo 3 perchè rispetta i vincoli, cioè c'è una variabile sulla sinistra poi c'è un simbolo terminale oppure un simbolo terminale con una variabile a destra.
ciauz!
Last edited by lSical on 11-06-2009 at 14:55
|
|
11-06-2009 14:51 |
|
|
| |
|
| saradid |
| io pero' sto vedendo la video lezione 6 ( parte 2) ... |
11-06-2009 15:37 |
|
|
saradid |
.grande:maestro.
Registered: Aug 2003
Posts: 753 (0.10 al dì)
Location:
Corso: Informatica Serale
Anno: 2
Time Online: 27 Days, 15:44:06: [...]
Status: Offline
Edit | Report | IP: Logged |
io pero' sto vedendo la video lezione 6 ( parte 2) e lei fa l'esempio proprio del linguaggio formato solo da parole pari con lettera a , quindi aa , aaaa, aaaaaaa tanto per intenderci.
Il linguaggio e' quello che dici tu , con a ^2n,
pero' il casino sorge quando dice , "proviamo a scrivere la grammatica che genera il linguaggio"....
come sigma ci mette a e va bene
poi come M dice S e va bene perche' e' l'assioma da cui parte tutto , ma ci mette anche A , questa A grande da dove salta fuori?!?!io mi perdo
|
|
11-06-2009 15:37 |
|
|
| |
|
| lSical |
| ... la mette perchè appunto utilizza altre regole ... |
11-06-2009 15:49 |
|
|
lSical |
.consigliere.
Registered: Mar 2008
Posts: 102 (0.02 al dì)
Location:
Corso: Informatica
Anno: 1
Time Online: 5 Days, 1:00:41 [...]
Status: Offline
Edit | Report | IP: Logged |
... la mette perchè appunto utilizza altre regole, infatti se non ci fosse non riuscirebbe a generare parole con a pari.
ex:
se parti con S->Aa
fai: Aa->aSa->aAaa->aaaa
questo vale per G={(a), (S,A), (S->Aa, A->aS, A->a), S}. (che poi la prima regola dovrebbe essere S->aA...almeno credo )
quindi è di tipo 3.
comunque l'esempio che ha fatto questo anno è più semplice 
infatti usa solo una variabile 
|
|
11-06-2009 15:49 |
|
|
| |
|
| saradid |
| all'esame lei da' un linguaggio , esempio a^n b^n ... |
11-06-2009 15:55 |
|
|
saradid |
.grande:maestro.
Registered: Aug 2003
Posts: 753 (0.10 al dì)
Location:
Corso: Informatica Serale
Anno: 2
Time Online: 27 Days, 15:44:06: [...]
Status: Offline
Edit | Report | IP: Logged |
all'esame lei da' un linguaggio , esempio a^n b^n e chiede di generare la grammatica , come si fa?cioe' come si stabilisce quali sono gli assiomi , le regole...io continuo a non capire i passaggi
|
|
11-06-2009 15:55 |
|
|
| |
|
| lSical |
| mmm... per quel linguaggio potresti anche arrivar ... |
11-06-2009 16:05 |
|
|
lSical |
.consigliere.
Registered: Mar 2008
Posts: 102 (0.02 al dì)
Location:
Corso: Informatica
Anno: 1
Time Online: 5 Days, 1:00:41 [...]
Status: Offline
Edit | Report | IP: Logged |
mmm... per quel linguaggio potresti anche arrivarci pensando un po...
comunque mi ricordo che aveva detto che all'orale si possono portare esempi fatti a lezione per dimostrare i vari tipi, quindi ti basta sapere un esempio per tipo, almeno lo spero
Last edited by lSical on 11-06-2009 at 16:08
|
|
11-06-2009 16:05 |
|
|
| |
|
| saradid |
| si ok , ma ad imparare a memoria sono capace, vorr ... |
01-07-2009 15:02 |
|
|
saradid |
.grande:maestro.
Registered: Aug 2003
Posts: 753 (0.10 al dì)
Location:
Corso: Informatica Serale
Anno: 2
Time Online: 27 Days, 15:44:06: [...]
Status: Offline
Edit | Report | IP: Logged |
si ok , ma ad imparare a memoria sono capace, vorrei capire come fare...
|
|
01-07-2009 15:02 |
|
|
| |
|
| fain182 |
| io non credo ci siano regole per passare da un lin ... |
01-07-2009 18:08 |
|
|
fain182 |
dsy newser
Registered: Apr 2008
Posts: 126 (0.02 al dì)
Location: Milano
Corso: informatica
Anno: 3
Time Online: 2 Days, 1:09:39 [...]
Status: Offline
Edit | Report | IP: Logged |
io non credo ci siano regole per passare da un linguaggio ad una grammatica..
normalmente tu scrivi una grammatica che genera un linguaggio..
poi magari con un po' di intuito puoi risalire alla grammatica che genera un linguaggio nei casi più semplici, ma per quello non c'è niente da imparare..
all'esame lei da' un linguaggio , esempio a^n b^n e chiede di generare la grammatica
oggi la palano non ha mai fatto domande del genere( è indispensabile invece prepararsi qualche esempio di grammatica )
|
|
01-07-2009 18:08 |
|
|
| |
|
| All times are GMT. The time now is 10:33. |
|
|
 |
|
 |
|
|
| |
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
|
|
|
|
|
|
alelorenz
