.dsy:it. - esempi di chomsky

.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- esempi di chomsky (http://www.dsy.it/forum/showthread.php?threadid=35787)

Posted by alelorenz on 12-07-2008 14:04:

esempi di chomsky

ciao... qualcuno riesce a farmi 4 veloci esempi di linguaggi da grammatiche di chomsky???

Posted by Nothingsoul on 28-09-2008 12:44:

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.

Posted by saradid on 04-06-2009 15:52:

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?

Posted by saradid on 10-06-2009 14:09:

qualcuno mi puo' aiutare? grazie

Posted by dieguito on 11-06-2009 12:51:

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

Posted by saradid on 11-06-2009 13:17:

speriamo che qualcuno ci illumini...senza esempi pratici questo esame non si capisce tanto...

Posted by lSical on 11-06-2009 14:51:

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!

Posted by saradid on 11-06-2009 15:37:

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

Posted by lSical on 11-06-2009 15:49:

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

Posted by saradid on 11-06-2009 15:55:

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

Posted by lSical on 11-06-2009 16:05:

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

Posted by saradid on 01-07-2009 15:02:

si ok , ma ad imparare a memoria sono capace, vorrei capire come fare...

Posted by fain182 on 01-07-2009 18:08:

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 )

All times are GMT. The time now is 01:09.

Show all 13 posts from this thread on one page