.dsy:it. - primi esercizi lfa

Pages (4): [1] 2 3 4 »
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)
-- primi esercizi lfa (http://www.dsy.it/forum/showthread.php?threadid=44046)

Posted by ele on 18-05-2016 12:59:

primi esercizi lfa

ciao ho da poco iniziato a studiare lfa in vista dell'esame di giugno con la prof Palano...ora ho provato a fare i primi esercizi di un tema d'esame e già crisi :cry:
dati i due linguaggi A = {0, 1}^∗ · {0} e B = {0, 1}^∗ · {1}
1) A ∩ B ?
2) A ∪ B = {0, 1}^∗?
3) A · B = B · A ?
4) A^∗ = A ∪ {ε} ?

risposte:

1) A ∩ B=Ø
2)si A ∪ B = {0, 1}^∗
3)no A · B != B · A
4)si A^∗ = A ∪ {ε}

Le risposte sono giuste?

Posted by Cronovirus on 18-05-2016 16:14:

Ciao Ele, non credo di riuscire ad aiutarti più di tanto perchè sono parecchio arrugginito in LFA e non escludo il fatto che possa dire cavolate. Comunque possiamo ragionare insieme su qualche punto:
1) perchè dici che l'insieme è vuoto? secondo me la stringa "1" è in entrambi i linguaggi ad esempio! Infatti i primi elementi di A dovrebbero essere A = {ε, 0,1,00,11,01,10,....} mentre quelli di B = {ε1, 01,11,001,011,101,etc..} dove ε1 è chiaramente equivalente a 1 (era per enfatizzare il fatto che{0, 1}^∗ può generare ε )
2) concordo
3) concordo
4) concordo

Posted by ele on 23-05-2016 19:27:

ciao grazie 1000 x la risposta ho un piccolo dubbio...ma scrivere a* è come dire {a}* giusto?

Posted by Cronovirus on 24-05-2016 16:30:

Originally posted by ele
ciao grazie 1000 x la risposta ho un piccolo dubbio...ma scrivere a* è come dire {a}* giusto?

Allora la definizione è che se a è un simbolo qualsiasi, allora a è una espressione regolare. Questa espressione denota il linguaggio {a}. Cioè L(a ) = {a}.

Quindi se vuoi una espressione regolare per il linguaggio {a}*, allora stai cercando a *. Ti ci ritrovi?

Posted by 857883 on 29-05-2016 20:09:

anche io sto provando a fare questi esercizi.
e avevo pensato all'insieme vuoto come risposta al primo esercizio...

Con la spiegazione di cronovirus(che ringrazio) sono arrivato a questo risultato:
A ∩ B = {0,1}
è corretto ?

Sapete dove posso trovare altri esercizi (oltre agli esami pubblicati nel sito)? magari con le soluzioni?

Posted by Cronovirus on 30-05-2016 00:47:

Sinceramente non ricordo la dimostrazione formale.. ma ci arrivo per ragionamento: intuitivamente A = {0,1}^* "contiene più stringhe" di B={0,1}^*{1}, basti pensare che A può generare stringhe che terminano con zero mentre B non può.

Per me insiemisticamente B è contenuto in A, quindi la risposta è proprio B. Infatti tutte le stringhe di B sono presenti anche in A.. prova ad elencare i primi elementi di B:

B = {ε1, 01,11,001,011,101,111,011....}

e è facile vedere che sono tutte anche in A! Scusa per la risposta poco formale, spero solo di non aver detto cavolate

Posted by Codo92 on 04-02-2017 16:12:

Posted by Codo92 on 04-02-2017 16:19:

ps: Esercizi corretti anche dalla Palano

Posted by yoham94 on 05-02-2017 11:55:

Ciao per caso hai appunti su queste cose? Perché sto preparando LFA ma non ho ancora capito bene come si fanno questi esercizi.
Grazie

Posted by Codo92 on 05-02-2017 12:37:

Originally posted by yoham94
Ciao per caso hai appunti su queste cose? Perché sto preparando LFA ma non ho ancora capito bene come si fanno questi esercizi.
Grazie

Ciao si, devo ridarla il 13

Io ho preso appunti dalle video lezioni e anche se sono un po' datate vanno bene ha detto la prof. Se hai dubbi posta qui qualcosa proviamo a farla assieme

Comunque per quanto riguarda questi esercizi si tratta solo di capire unione, intersezione, complemento... non è nulla di impossibile

ps: Stavo facendo un riassunto, nel caso, se mi viene bene, lo uploado

Posted by yoham94 on 05-02-2017 14:47:

per caso hai le soluzioni del tema d'esame di gennaio?

Posted by Codo92 on 05-02-2017 16:39:

Originally posted by yoham94
per caso hai le soluzioni del tema d'esame di gennaio?

No, l'ho fatto ma non l'ho passato purtroppo. Il problema è che erano più domande di teoria che altro, mi hanno abbastanza spiazzato

Per la precisione c'erano (ho visto che sul sito della Palano non c'è il tema quindi le scrivo qui):

1) Due esercizi come quello di questo 3d
2) Scrivere una grammatica di tipo 3 per il linguaggio A (A è un linguaggio dato per i primi due esericizi del punto 1)
3) Dati A e complemento di A ricorsivamente numebrabili, A è ricorsivo? (sinceramente è la domanda che mi ha messo più in difficoltà)
4) Dare definizione formale di automa massimo
5) Descrivere i passaggi per passare da automa massimo a automa minimo
6) Data una grammatica G... disegnare un automa a pila e descrivere la tecnica usata per ricavarlo

Appena finito il riassunto poi lo comunico, ci metto anche le (mie) soluzioni ai temi d'esame che ha sul sito + quello di gennaio (che è praticamente un ripasso di tutto...)

Posted by yoham94 on 06-02-2017 14:51:

io i temi d'esame compreso quello di gennaio li ho fatti così.
fammi sapere se secondo te c'è qualcosa di sbagliato

Posted by Codo92 on 06-02-2017 17:08:

Ciao ho guardato però ti rispondo domani che ancora non ho completato tutto, c'erano un paio di cose che non hai fatto che provo a mettere io così vedi se ti quadrano... domani guardo con più attenzione perchè oggi non ce la faccio

Posted by Codo92 on 09-02-2017 11:34:

Ciao, chiedo scusa per il mega ritardo purtroppo ho avuto una settimana da inferno! Oggi mi dedico esclusivamente ad LFA quindi ci sono

Intanto ho qui parte di un riassunto che sarebbe da completare: manca una parte nel primo foglio alla quale non voglio rispondere perchè ammetto la mia ignoranza.
Per il resto si tratta solo della difficoltà di disegnare correttamente il tutto. Se mancano degli argomenti che ritenete importanti aggiungete pure e riuploadate.

Oggi vedo di fare i temi d'esame, se riesco su pdf. Vedo di uploadare pomeriggio/stasera.

All times are GMT. The time now is 09:19.

Pages (4): [1] 2 3 4 »
Show all 47 posts from this thread on one page