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

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?

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

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

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

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?

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

ps: Esercizi corretti anche dalla Palano

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

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

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

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

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

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

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.

Ciao riupploado il file con le tracce svolte perchè mi sono accorto che alcune pagine mancavano. Carico anche un riassunto che ho fatto sperando possa essere utile, purtroppo è fatto a mano quindi non so quanto si riesca a capire cosa c'è scritto

Fatto il primo tema d'esame. Stasera se riusciamo facciamo uno zippone e uploadiamo nella giusta sezione così facciamo ordine

Pomeriggio vedo di fare gli altri

Secondo tema

Terzo tema

perdonate la disgrafia. Utilizzando un editor online per di più non riesco a fare le frecce, devo andare di mano libera... già con la penna faccio schifo, figuriamoci col mouse

Quarto tema

Se qualcuno nota perplessità è pregato di farlo presente

ps: stasera o domani mattina vedo di caricare anche io le soluzioni per l'ultimo tema d'esame così si può fare un confronto.

Ciao ho confrontato i primi 2 temi d'esame con i miei.
Nel primo, l'automa dell'esercizio 5 credo sia giusto il mio.
Nel secondo, potresti spiegarmi l'esercizio 1 e il 5b?


Nel tema d'esame del 170715 la risposta che ho dato alla domanda 2 è sbagliata quindi puoi anche non considerarla

Originally posted by yoham94
Ciao ho confrontato i primi 2 temi d'esame con i miei.
Nel primo, l'automa dell'esercizio 5 credo sia giusto il mio.
Nel secondo, potresti spiegarmi l'esercizio 1 e il 5b?

Originally posted by Codo92
No, nel tuo manca stato trappola ed inoltre hai aggiunto uno stato finale {f}. Quando leggi a,b in {f,p} ritorni in f che è appunto in {f,p}. Ti quadra?

Originally posted by yoham94
Sullo stato trappola sono d'accordo, ma se io sono in {f,p} e leggo a,b vado in {f} perchè f su input a,b va in f ma p su input a,b non va da nessuna parte quindi hai {f} unione {insieme vuoto} = {f}

Originally posted by Codo92
Se leggi qualcosa che ritorna nello stato che hai già non c'è necessità di crearne uno nuovo per distinguerlo. Proprio perchè su f con input a,b ritorni in f non c'è bisogno di riscrivere un nuovo stato. Se p con a,b andasse in un altro stato potrei darti ragione, creeresti lo stato {f, altro stato} ma così ripeto che ritorna nello stato in cui è già. Tu hai creato {f, insieme vuoto}

Originally posted by yoham94
Io mi sono basato su questo esempio che ha fatto nelle videolezioni, lo stato {q0,q3} su input a va in {q3} non rimane in {q0,q3}

Originally posted by Codo92
Prendi come esempio lo stato {Q1, Q2} vedi con la b come fa (sempre in questo esercizio delle videolezioni).

Comunque adesso cerco una spiegazione chiara, sono sicuro della correttezza perchè questo lo avevo fatto correggere alla prof.

Il resto che mi hai chiesto ti è chiaro invece?

Guarda sui primi due temi sono sicuro al 99,9% (me li ha corretti la prof. entrambi, mi hai messo il dubbio su quell'automa ma così gliel'ho presentato e così le andava bene). Per il 5b sono solo quelle degli stati irraggiungibili le regole da eliminare (anche perchè per esempio poi leggendo dallo stato iniziale 'b' dove vai se elimini P? Se lo fai a S invece non ti fai alcun problema perchè tanto è uno stato che non raggiungerai mai). Ci riaggiorniamo domani mattina Buona serata, vedi se anche gli altri due temi ti convincono o c'è qualcosa che per te è sbagliato

Originally posted by Codo92
Guarda sui primi due temi sono sicuro al 99,9% (me li ha corretti la prof. entrambi, mi hai messo il dubbio su quell'automa ma così gliel'ho presentato e così le andava bene). Per il 5b sono solo quelle degli stati irraggiungibili le regole da eliminare (anche perchè per esempio poi leggendo dallo stato iniziale 'b' dove vai se elimini P? Se lo fai a S invece non ti fai alcun problema perchè tanto è uno stato che non raggiungerai mai). Ci riaggiorniamo domani mattina Buona serata, vedi se anche gli altri due temi ti convincono o c'è qualcosa che per te è sbagliato

Originally posted by yoham94
Ultima domanda per oggi secondo tema d'esame esercizio 4a terza domanda perché hai messo no?

Quinto tema (23 gennaio)

Non garantisco la correttezza degli esercizi (Dubbi sull'automa a pila - la funzione - e qualcosa nel primo esercizio)

Originally posted by Codo92
Quinto tema (23 gennaio)

Non garantisco la correttezza degli esercizi...

Originally posted by yoham94
Confermo anch'io ho fatto così, nel pomeriggio cerco di riguardare i temi mancanti e poi ti faccio sapere se qualcosa non mi torna

Originally posted by Codo92
Di diverso abbiamo solo due cose, una è la grammatica di tipo 3, dovrebbero essere corrette entrambe, l'altra cosa è sull'automa a pila, con B su input b, io ho messo parola vuota la

Originally posted by yoham94
Si si B su input b è parola vuota la mia è stata una svista. Allora ricontrollo anche la grammatica di tipo 3

Originally posted by Codo92
Terzo tema

perdonate la disgrafia. Utilizzando un editor online per di più non riesco a fare le frecce, devo andare di mano libera... già con la penna faccio schifo, figuriamoci col mouse

Originally posted by Codo92
Quarto tema

Se qualcuno nota perplessità è pregato di farlo presente

ps: stasera o domani mattina vedo di caricare anche io le soluzioni per l'ultimo tema d'esame così si può fare un confronto.

Originally posted by yoham94
Confermo tutto tranne l'ultimo esercizio che io ho fatto così
ah ovviamente come avevo già detto c'è da eliminare la mia soluzione all'esercizio 2

Originally posted by Codo92
Quindi dici che va bene quella che ho messo io nel secondo esercizio? Per il quinto, devo dire che il tuo mi piace, credo siano giusti entrambi, la differenza sta nel fatto che nello stato finale, io mando nello stato trappola se arrivano altri 0,1 tu fai ricominciare il giro (più che giusto, anzi anche più bello da vedere). L'importante è che faccia ciò che è richiesto quindi suppongo ci siano infiniti altri possibili automi da poter fare. Sei d'accordo o trovi qualche errore nel mio?

Originally posted by yoham94
Sulla domanda due non saprei perché lei chiede un esempio mentre tu hai messo la spiegazione, credo che piuttosto che non mettere nulla vada bene quello che scritto tu.

Sul riassunto che avevo postato hai qualche aggiunta da fare?

Mi pare ci sia tutto più tardi gli do una occhiata con più attenzione

Ho fatto questo riassunto prendendo spunto anche dalle domande dei temi d'esame, spero possa essere utile A domani!

Edit: Mi sono accorto di un errore nella definizione di linguaggio ricorsivamente numerabile: se x appartiene a L -> 1 altrimenti loop...

Com'è andata? (8 RITIRATI!!!!) A quanto pare adesso gli esami non sono più come quelli che ha sul suo sito. E' tutta teoria. Due esercizi come al solito sui linguaggi, definizione formale della moltiplicazione di A per B, Teorema dell'inclusione e commentarlo, Disegnare automa data una grammatica, commentare il procedimento per ricavarlo e ricavarne una espressione regolare e infine dare l'automa a pila per la grammatica G

Originally posted by Codo92
Com'è andata? (8 RITIRATI!!!!) A quanto pare adesso gli esami non sono più come quelli che ha sul suo sito. E' tutta teoria. Due esercizi come al solito sui linguaggi, definizione formale della moltiplicazione di A per B, Teorema dell'inclusione e commentarlo, Disegnare automa data una grammatica, commentare il procedimento per ricavarlo e ricavarne una espressione regolare e infine dare l'automa a pila per la grammatica G

Purtroppo no, ho sbagliato gli esercizi su automa a pila, classica roba che consegni e ti rendi conto della ca***ta fatta appena chiedi ai tuoi amici che risposte hanno messo... E devo aver sbagliato qualcos'altro ma non so dove... infatti prenderò colloquio per vedere -.-

chi ha postato questi temi svolti della palano sono errate alcune parti qualcuno avrebbe le soluzioni corrette per favore?? ho l'esame domani è urgente