ele

User info:

Registered: May 2016
Posts: 5 (0.00 al dì)
Location:
Corso: informatica
Anno:
Time Online: 2:35:54 [...]
Status: Offline

Post actions:

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

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.11 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

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

ele

User info:

Registered: May 2016
Posts: 5 (0.00 al dì)
Location:
Corso: informatica
Anno:
Time Online: 2:35:54 [...]
Status: Offline

Post actions:

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

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.11 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

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

Last edited by Cronovirus on 24-05-2016 at 16:34

857883

User info:

Registered: Nov 2014
Posts: 11 (0.00 al dì)
Location: milano
Corso: informatica
Anno: 1
Time Online: 7:21:58 [...]
Status: Offline

Post actions:

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?

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.11 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

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

Codo92

User info:

Registered: Jan 2013
Posts: 42 (0.01 al dì)
Location:
Corso: \
Anno: \
Time Online: 1 Day, 10:22:28 [...]
Status: Offline

Post actions:

Originally posted by ele
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
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?

Codo92

User info:

Registered: Jan 2013
Posts: 42 (0.01 al dì)
Location:
Corso: \
Anno: \
Time Online: 1 Day, 10:22:28 [...]
Status: Offline

Post actions:

ps: Esercizi corretti anche dalla Palano

yoham94

User info:

Registered: Oct 2013
Posts: 16 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 12:27:09: [...]
Status: Offline

Post actions:

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

Codo92

User info:

Registered: Jan 2013
Posts: 42 (0.01 al dì)
Location:
Corso: \
Anno: \
Time Online: 1 Day, 10:22:28 [...]
Status: Offline

Post actions:

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

yoham94

User info:

Registered: Oct 2013
Posts: 16 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 12:27:09: [...]
Status: Offline

Post actions:

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

Codo92

User info:

Registered: Jan 2013
Posts: 42 (0.01 al dì)
Location:
Corso: \
Anno: \
Time Online: 1 Day, 10:22:28 [...]
Status: Offline

Post actions:

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

Last edited by Codo92 on 05-02-2017 at 17:38

yoham94

User info:

Registered: Oct 2013
Posts: 16 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 12:27:09: [...]
Status: Offline

Post actions:

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

Attachment: temi svolti.pdf
This has been downloaded 50 time(s).

Codo92

User info:

Registered: Jan 2013
Posts: 42 (0.01 al dì)
Location:
Corso: \
Anno: \
Time Online: 1 Day, 10:22:28 [...]
Status: Offline

Post actions:

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

Codo92

User info:

Registered: Jan 2013
Posts: 42 (0.01 al dì)
Location:
Corso: \
Anno: \
Time Online: 1 Day, 10:22:28 [...]
Status: Offline

Post actions:

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.

Attachment: lfa riassunto teoria da completare.pdf
This has been downloaded 51 time(s).