.dsy:it. - [LFA] Dubbi 2002

Pages (2): « 1 [2]
Show 150 posts per page

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

Posted by turbolenza on 22-08-2002 09:39:

Linguaggi RE

Nelle dispense di LFA a pag. 5 si dice che
"esistono linguaggi RE (ricorsivamente enumerabili) il cui complemento non
e' RE".

Un linguaggio L ricorsivamente enumerabile e' semidecidibile ovvero:
esistono delle stringhe su Sigma* per cui X(S) non termina
esistono delle stringhe su Sigma* per cui X(S) termina

Il linguaggio complemento Lc non ha anchesso le stesse caratteristiche?
esistono delle stringhe su Sigma* per cui X(S) non termina
esistono delle stringhe su Sigma* per cui X(S) termina

D'altra parte la negazione di X(S) di L riconosce Lc. Quindi X(S) e
negazione X(S) hanno lo stesso comportamento, quindi riconoscono entrambi
due linguaggi RE.

Dove sbaglio?

Posted by Lunik on 24-08-2002 12:51:

Ciao Turbolenza!! Ma durante le vacanze ti :cannabis??
A parte che Ric Enumerabili NON ESISTE!! Caso mai sn NUMERABILI!!!!! :wink:
Quello ke hai scritto è incomprensibile x me in questo momento, xò ti conviene leggerti BENE quel ke c'è sulle dispense.
Hai un L che è RN...il LC non lo è.
Allora L NON è Ricorsivo...se lo fosse anke LC dovrebbe esserlo, e dovrebbe essere quindi RN.
Tu dici anche che "Un linguaggio L ricorsivamente enumerabile e' semidecidibile "...ehm, ma NUMERABILE e SEMIDECIDIBILE sn la STESSA COSA!
E' il Linguaggio di partenza che nn è ricorsivo...
Nn capisco il tuo problema.... :pensa:
Nn è ke x caso fai un salto in silab in questi giorni?????

__________________
Il DSY su Facebook!!!

Posted by turbolenza on 27-08-2002 12:27:

Linguaggi RE

Ach! Faccio un po' fatica a leggere i msg con cosi' tante abbreviazioni e espressioni idiomatiche. Comunque sia:

["Ricorsivamente Enumerabile" versus "Ricorsivamente Numerabile"]
Sono espressioni equivalenti ed utilizzate correntemente entrambe. La prima mi sembrerebbe piu' corretta (ma sarebbe lungo dire il perche') e tendo a preferirla anche perche' l'abbreviazioni che si usa normalmente per un linguaggio ricorsivamente enumerabile o numerabile che dir si voglia e' "linguaggio RE".

Se fai una ricerca in rete su google

"ricorsivamente enumerabile" --> 48 occorrenze
"ricorsivamente numerabile" --> 10 occorrenze

o usando i plurali

"ricorsivamente enumerabili" --> 94 occorrenze
"ricorsivamente numerabili" --> 13 occorrenze

[Semidecidibile e ricorsivamente enumerabile]
No, non sono la stessa cosa. Ma si dimostra che se un linguaggio e' RE allora e' semidecidibile. Riporto due definizioni (sono imprecise)

- si dice _ricorsivamente enumerabile_ un insieme (infinito) i cui elementi sono generabili da un automa
- si dice semidecidibile un linguaggio per cui esiste un processo costituito da un numero finito di passi che porta a riconoscere quando una stringa fa parte linguaggio ma non quando quando una stringa non fa parte del linguaggio

No, per il momento non passo dal Silab. Verro' direttamente per il prossimo appello. A proposito si sa qualche cosa di quando sara' il prossimo appello di Bertone?

Salutoni e baci, W.

Posted by Lunik on 27-08-2002 12:37:

Caro Turbolenza, ma SU COSA stai studiando LFA??? :pensa:
spero che nn stai cercando su internet appunti, libri su Lfa!!!!! :lol: se no diventi :pazzo: !!!
Cmq, appena inizierò a fare LFA seriamente ( :lol: ) ti risponderò ai dubbi...caso mai, manda mail a Bertoni....... :ciao:

__________________
Il DSY su Facebook!!!

Posted by turbolenza on 27-08-2002 13:56:

Ho mandato una mail a Bertoni... ma non mi ha risposto!!!
C'e' qualche indirizo segreto che debbo usare??
Sai nulla della data del prossimo appello?

Salutation, W.

Posted by Lunik on 27-08-2002 13:58:

Sarà in vacanza....sicuro!
Date?
Beh l'appello ufficiale è il 23, qualcuno xò mi parlava anke del 2 settembre.....cmq continuerà a fare appelli ogni lunedì...... :ciao:

__________________
Il DSY su Facebook!!!

Posted by rostich on 16-09-2002 10:00:

Una domanda per la inclusione delle grammatiche.
Sappiamo ke la R2 e' un dottogruppo prorpio di R1, quindi tutti gli elementi della R2 appartengono a R1 ma non vale il viceversa.

R1 mi dice che l(b)>l(a), e mi dice pure che e' accettato S->Epsilon (parola vuota) solo se assioma S non comparira' nella parte d di un'altra regola (Infatti questa S->epsilon e' una eccezionein quanto l(S)=1 e l(epsilon)=0, quindi l(b)<l(a)).

R2 mi richiede solamente ke la parte sx (a) sia un metasimbolo. Ok!
Quindi so ho S->espilon e' sia in R1 che in R2. Ma se ho poi nella stessa grammatica S->SS (come da esempio nelle dispense), allora questa fa parte di R2 ma non di R1 (in quanto ho S->epsilon ma poi S compare a dx), ke e' assurdo per ipotesi! QUINDI?!?!?!!??

Vi prego, c'e' sicuramente un errore nel mio ragionamento, ma dove!????!??!
Thanks, Rostich

Posted by turbolenza on 16-09-2002 13:04:

Grammatiche ed epsilon

E' un altro dei numerosi punti in cui le dispense sono assolutamente incomprensibili.
Se vuoi davvero capire come funziona la cosa, prenditi un testo serio.
Ti do' tuttavia un piccolo spunto sperando di dire cose corrette e compresnibili:

- Le grammatiche vengono talvolta definite escludendo le produzioni che generano epsilon (probabilmente per rendere piu' semplice [ortogonale?] la descrizione sintattica delle produzioni)
- Tuttavia e' ragionevole (ed evito di entrare nei dettagli) considerare un lingaggio di un certo tipo a prescindere che questo contenga o meno l'elemento epsilon.
- Quello che allora si fa a volte e': dare la forma delle produzioni delle grammatiche >=r1 in modo che non generino epsilon. Quindi mostrare in qualche modo che e' possibile considerare anche questo tipo di produzione senza che la grammatica perda le sue caratteristiche.

Parto per il Giappone. Non rispondero' ad eventuali repliche. Addio.[/i]

Posted by Sayan on 17-09-2002 10:33:

Ho appena iniziato a std LFA e leggendo un po' i vari dubbi......Innanzitutto ho letto una delle prime domande sul xchè un L ricorsivo è anche ric.numerabile.
La DIM mi sembra abba semplice, se L è ricorsivo(e quindi x def esiste un alg ke riconosce L definiamo una procedura ke partendo dalla prima parola in ordine Ranking e scorrendole tutte in un ciclo anzikè restituire 1 o 0 a seconda ke la parola appartenga o no a Sigma nn fa altro ke stamparla(e qst nn è altro ke la Def di L ric.numerabile)

Posted by Sayan on 17-09-2002 16:11:

MA c'è qualcuno ke lo darà a qst appello??????
Sto a pazzià......
Ok ke se L è Ric è anche Ric-Num
Ok ke L Ric allora Lc Ric
MA nn capisco la DIM del fatto ke se L è Ric-Num allora Lc NN lo è
: : : :
Ne sapete qlcs a riguardo???

Posted by rostich on 18-09-2002 11:46:

Carissimo, la dimostrazione non e' ke se L e' ric num allora Lc non lo e'.
La dim. e' ke se un L e' ric num E IL SUO COMPLEMENTO Lc NON LO E' allora Lc non e' ricorsivo.

DImostriamolo x assurdo. Se L fosse ricorsivo allora anke Lc e' ricors. e quindi Lc e' anke ric. num. Errore , in quanto abbiamo detto prima ke un L ric. num. con Lc non ric. num. non e' ric. Dal momento ke se L fosse ric. avremmo ke il suo complemento lo e' pure (ric.) , ma va contro cio' ke abbiamo assunto in precedenza.
Spero ke tu abbia capito.

Io ci provo lunedi', anke se ho un paio di dubbi (VEDI DIM. DELLA SECONDA PARTE DI KLEENEX! SCUSATE LA BATTUTA POCO SIMPATICA). :roll:
Ciauz!

Posted by Sayan on 18-09-2002 14:04:

La DIM nn fa una grinza.....perfect, mi ero posto in maniera errata il problema.
Io nn so se lo tento, tu quando hai iniziato a std??
Hai gia finito??

THANKS x la DIM 8-)

Posted by Sayan on 18-09-2002 14:08:

....nn x essere indiscreto...... ma di nome fai A....... bè manteniamo la privacy, ma mi sa proprio ke ci conosciamo. .........

Posted by rostich on 19-09-2002 11:40:

NO,mi kiamo Fabio! Mi sa ke non ci conosciamo!
Comunque in 10 giorni e' fattibile da preparare (be', forse 15). iL problema reale e' nel capire le dispense (SCUSATE MA FATTE MALE E CON DEGLI ERRRORI). Capite quelle non ci sono grossi problemi.
Sapete quanti sono iscritti circa x il 23 settembre. C'e' anke goldrake (visto ke lui l'esame l'ha fatto il 19 non penso ci sia)?.
Grazie a tutti!

Posted by Lunik on 19-09-2002 11:42:

x me NOn vi conoscete...non saprai mai in quanti siete il 23, xè tanto...uno può arrivare anke il 23 stesso e mettersi "in lista d'attesa" :lol: :lol: :lol: eheheh in bocca al lupo!:wink:

__________________
Il DSY su Facebook!!!

Posted by Sayan on 19-09-2002 14:01:

Arghhhh, ero convinto fossi un altro, heehhe.
Cmq io sto std sulle dispense ke hanno fatto dei ragazzi del corso di Goldrake, sn fatte molto meglio.

Posted by Serpico on 19-09-2002 14:57:

...

secondo me ti incasini dippiù...(non perchè siano fatte male, anzi, ma perchè hai poco tempo e il materiale è fin troppo) cmq se devi fare l'esame con gold vanno benissimo...
se invece lo devi fare con bert1s (bertoni) allora guardati solo le sue e semmai quello che non capisci vai ad approfondirlo in altre dispense (se proprio devi)
fai così sennò impieghi più del dovuto. :ciao:

__________________
~"sicurezza... oscurità... solo un altro sballato... in un mondo di sballati." (paura & delirio a Las Vegas)
~"C'HO CERTI CAZZI MAFA' CHE NEMMENO TU CHE SEI PRATICA LI HAI VISTI MAI..." (Proietti in Febbre da cavallo)
~"Il segno si decifra l'apparenza non si decifra. Non si deve assolutamente decifrare, non esiste proprio al mondo che l'apparenza si decifri" (Grande Max Mazzotta in PAZ )
~"Sono un eroe, perché lotto tutte le ore Sono un eroe perché combatto per la pensione Sono un eroe perché proteggo i miei cari dalle mani dei sicari dei cravattari Sono un eroe perchè sopravvivo al mestiere Sono un eroe straordinario tutte le sere Sono un eroe e te lo faccio vedere Ti mostrerò cosa so fare col mio super potere" (Capa)

Posted by Sayan on 19-09-2002 15:09:

Il problema è ke quelle di Bert1s nn sn chiarissime, o meglio, se nn hai seguito il corso nn è ke le capisci molto, invece nelle altre ci sn esempi ke ti chiariscono un po di + Dim e DEf......io cmq me le sto guardando tutte e 2 , tanto mi sa ke lo daro ad ottobre xchè x lun nn credo di farcela.
Poi mi hanno detto ke è anche abba largo nei voti, quindi un bel voto nn guasterebbe....hehehe
Cmq THANKS x il suggerimento

Posted by Serpico on 19-09-2002 15:12:

...

cmq alla fine ci sono termini diversi tra le dispense per dire la stessa cosa (e anche il programma è diverso e le cose da studiare),è per quello che ti consigliavo di studiare solo quelle di un prof (quelle del prof con cui devi fare l'esame)
io l'ho preparato in un mese, ma 15 gg bastano se studi a fuoco

Posted by Sayan on 19-09-2002 15:15:

Gia quello dei termini diversi potrebbere essere un problema, x il resto è vero ke bert1s fa fare l'exam anche nel suo studio su appuntamento??
...mi pare di averlo letto da qlc parte qui in giro...

Posted by Serpico on 19-09-2002 15:27:

...

l'ho letto anch'io, ma non te lo posso confermare, per quanto mi riguarda io l'ho fatto in uno dei tanti monday bloody monday

Posted by Sayan on 19-09-2002 15:36:

Bè magari quando sn al silab gli faccio una visita, oppure gli mando una mail informativa......

Posted by Lunik on 19-09-2002 15:38:

mandargli una mail è una cosa da evitare xè nn sai se risponde, meglio andare da lui in ufficio e chiedediglielo :wink:

__________________
Il DSY su Facebook!!!

Posted by Serpico on 19-09-2002 15:45:

...

infatti, all'esame l'aveva raccomandato di non mandargli mail per qs "cosa" (lui aveva usato un altro termine... ) meglio il ricevimento, è più disponibile.

Posted by Sayan on 19-09-2002 16:30:

Ok allora gli faccio una visitina la prox sett

Posted by rostich on 19-09-2002 17:50:

OK!
Raga ma io non sapevo ci fossero 2 tipi di dispense diverse! QUindi, mi date gli indirizzi URL (termine informatico fichissimo ) delle disp. di BertUnix e Goldrake?
Grasssie!

Posted by Lunik on 19-09-2002 17:53:

http://homes.dsi.unimi.it/~goldwurm/ling/
vero la metà della pagina trovi dispensa d Goldrake..

x Bertoni:
http://webcen.usr.dsi.unimi.it/2001.../lfa/index.html

__________________
Il DSY su Facebook!!!

Posted by Lunik on 19-09-2002 18:18:

cosa c'entra la storia dei turni nel topic su LFA????

__________________
Il DSY su Facebook!!!

Posted by Sayan on 19-09-2002 18:22:

ops.....

Posted by Sayan on 19-09-2002 18:34:

Lunik nn posso toglierlo il mex???

Posted by Lunik on 19-09-2002 18:37:

tolto xò ora dimmi ke senso hanno i nostri post! :pensa: