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

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....
Nn è ke x caso fai un salto in silab in questi giorni?????

__________________
Il DSY su Facebook!!!

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.

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

__________________
Il DSY su Facebook!!!

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.

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

__________________
Il DSY su Facebook!!!

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

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]

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)

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

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

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

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

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!

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" eheheh in bocca al lupo!:wink:

__________________
Il DSY su Facebook!!!