 | |
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 |
esempi di chomsky
Clicca QUI per vedere il messaggio nel forum |
| alelorenz |
| ciao... qualcuno riesce a farmi 4 veloci esempi di linguaggi da grammatiche di chomsky??? |
| Nothingsoul |
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. |
| 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? |
| saradid |
| qualcuno mi puo' aiutare? grazie |
| dieguito |
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... |
| saradid |
| speriamo che qualcuno ci illumini...senza esempi pratici questo esame non si capisce tanto... |
| lSical |
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! |
| saradid |
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 |
| lSical |
... 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 ;) |
| saradid |
| 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 |
| lSical |
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 :) |
| saradid |
| si ok , ma ad imparare a memoria sono capace, vorrei capire come fare... |
| fain182 |
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 ) |
|
|
|
|
