.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- [LFA] Dubbi 2002 (http://www.dsy.it/forum/showthread.php?threadid=249)

Linguaggi formali e automi-DUBBI

Ciao a tutti , avrei due dubbi da chiedervi:
mi sapreste dare un esempio di un linguaggio di tipo 3 generato da una grammatica lineare a destra ?
Inoltre, dalla dimostrazione della proposiz 5.1 delle dispense("se L e generato da una grammatica lineare a dx,allora e di tipo 3") perchè col procedimento descritto nei punti 3 e 4 si possono eliminare regole del tipo A->B??
Grazie 1000!

Per la 1a domanda...credo ci sia un esempio nelle dispense...controlla un po'...
x la 2a...beh, devo ancora studiare!!!!

__________________
Il DSY su Facebook!!!

Re: Linguaggi formali e automi-DUBBI

Originally posted by "kikka"

Inoltre, dalla dimostrazione della proposiz 5.1 delle dispense("se L e generato da una grammatica lineare a dx,allora e di tipo 3") perchè col procedimento descritto nei punti 3 e 4 si possono eliminare regole del tipo A->B??

__________________
Teju.it - Una vita da raccontare

Ciao,intanto grazie x avermi risposto.
Si mi riferisco alle dispense di webcen è la dimostrazione della proposizione 5.1 del 1 capitolo.
Che non capisco sono gli ultimi 3 punti dove aggiunge regole per eliminare la A->B
..sono un po lunghe da scrivere cmq se non le trovi le scriverò.
In effetti mi sono accorta che di 5.1 ce ne sono un po non avevo specificato che mi riferivo al 1 capitolo!

linguaggi ricorsivi e ricorsivam numerabili

Ciao! Approfitto del thread per fare una doamnda anche io: NON riesco a capire questa implicazione.....
"Se un linguaggio e' ricorsivo, allora e' anche ricorsivamente numerabile"
Anzi nelle dispense si dice "chiaramente, se un L e' ricorsivo, allora e' ricorsivamente numerabile"
Ma chiaramente un tubo.....non ci arrivo....magari e' davvero una banalita'......
Qualcuno sa aiutarmi?

Semplice!
1)Se L ha riconoscitore, ha ANKE generatore
2)L ha riconoscitore allora è RICORSIVO
3)L ha generatore è RICORSIVAM NUMERABILE
4)Quindi se è ricorsivo è anke ric numerabile...

chiaro?

__________________
Il DSY su Facebook!!!

no

non e' chiaro..scusa se rompo...pero' quello che non mi e' chiaro e' la prima implicazione...perche' se L e' riconoscitore ha anche generatore???? 8O
Nella def di metodo riconoscitivo si dice che un L ha un riconoscitore se esiste un algo A che presa una parola w da 1 se w appartiene a L e 0 se w non appartiene a L...cioe' A calcola la funzione caratteristica di L su w.......ma non si dice che ha anche un generatore......

guarda la dispensa in formato pdf e guarda in fondo alla 4a pagina (la sto studiando adesso...)

c'è scritto che se L ha riconoscitore ha anche generatore...

__________________
Il DSY su Facebook!!!

e' quello che dico.....infatti sulla dispensa si dice "chiaramente se l ha riconoscitore ha anche un generatore" beh e' proprio questo che non mi e' chiaro......se L ha un riconoscitore da cosa deduco che ha anche un generatore??????
Devo prendere l'implicazione come una definizione senza capirla? ci sara' un motivo.......

se c'è un metodo che mi riconosce un L...L da chi caxxo è stato generato????

__________________
Il DSY su Facebook!!!

a me invece mi puzza il fatto che se L ha generatore nn possa aver necessariamente un riconoscitore...povero L...mi fa quasi pena!!!!!

__________________
Il DSY su Facebook!!!

Re: Linguaggi formali e automi-DUBBI

Originally posted by "kikka"


Inoltre, dalla dimostrazione della proposiz 5.1 delle dispense("se L e generato da una grammatica lineare a dx,allora e di tipo 3") perchè col procedimento descritto nei punti 3 e 4 si possono eliminare regole del tipo A->B??

__________________
Teju.it - Una vita da raccontare

come nn kiede dimo???? almeno bisogna sapere in linea generale come farla....sbaglio????????????????????????

__________________
Il DSY su Facebook!!!

DUBBIONE!!

Le regole d produz sn del tipo A->B
A appartiene a (S U Q)
ma QUELLA S e' l'assioma o l'alfabeto S (che poi conosciamo come SIGMA??????????)

tnx[/code]

__________________
Il DSY su Facebook!!!

Originally posted by "Lunik"

come nn kiede dimo????

__________________
Teju.it - Una vita da raccontare