| Autore |
 Discussione  |
|
|
Stefo
Utente giovane
Regione: Puglia
Prov.: Brindisi
Città: Brindisi
|
 Inserito il - 02/09/2006 : 11:32:27
|
In alcuni appelli di LOPS viene chiesto di Dimostrare Formalmente che il linguaggio dato, L, non sia lineare destro.
La Dimostrazione va fatta con il pumping lemma dei linguaggi regolari?
Spesso nelle vecchie tracce ho notato che chiede di che tipo e' il linguaggio dato, come faccio a rispondere? Devo trovarmi la grammatica che lo genera e poi specificare il tipo secondo la gerarchia di Chomsky?
|
|
|
n/a
deleted
Prov.: Bari
|
 Inserito il - 02/09/2006 : 13:12:18
|
Ti rispondo come uno che ha fatto linguaggi 3 anni fa'
Citazione:
Messaggio inserito da Stefo
In alcuni appelli di LOPS viene chiesto di Dimostrare Formalmente che il linguaggio dato, L, non sia lineare destro.
La Dimostrazione va fatta con il pumping lemma dei linguaggi regolari?
Si, pero' in alcune situazioni conviene risolverlo con la concatenazione di linguaggi piu' semplici o con quell'altra cosa che si basava sulla lunghezza delle produzioni, ma non so se Lops lo permette
Citazione:
Spesso nelle vecchie tracce ho notato che chiede di che tipo e' il linguaggio dato, come faccio a rispondere? Devo trovarmi la grammatica che lo genera e poi specificare il tipo secondo la gerarchia di Chomsky?
E si, se il linguaggio e' lineare destro puoi trovare l'espressione regolare corrispondente, probabilmente pero' in alcuni casi in cui non e' evidente la corrispondenza tra grammatica e linguaggio ti serve dimostrare (credo per induzione) che L(g) = L |
 |
|
|
Stefo
Utente giovane
Regione: Puglia
Prov.: Brindisi
Città: Brindisi
|
 Inserito il - 02/09/2006 : 17:51:20
|
| Era quello che volevo sentire! |
|
|
| |
Discussione |
|
|
|
Dimostrare... Formalmente
