| V I S U A L I Z Z A D I S C U S S I O N E |
| gym83s |
Inserito il - 26/01/2006 : 14:40:05
Ciao Ragazzi, questo è il consueto appuntamento post-esame dove come al solito si chiariscono gli esercizi......
peccato però che sia ancora io a postare questo...
quando sarà il giorno che LINGUAGGI sarà MIO????mmah ad ogni modo le tracce di oggi erano:
1.1) Dimostrare formalmente che il linguaggio
L={a^j b^k c^k: 0<=j<=k} non è un linguaggio lineare destro.
(Se non sbaglio si usa il Pumping Lemma per i linguaggi regolari..o no??)
1.2) Stabilire se L è libero da contesto.Dimostrare formalmente la risposta. (come si faceva?? Il pumping Lemma c.f.??non riesco a capirlo...)
2) Progettare, commentando opportunamente l'automa riconoscitore a stati finiti per il seguente linguaggio:
L={w e {0,1,2}* : |w| =2k+1, k>0}
(e questo??? chi l'ha fatto?? Io no.........)
Se qualcuno ha svolto qualcuno degli esercizi risponda please......
CIAOOOO
|
| 20 U L T I M E R I S P O S T E (in alto le più recenti) |
| gym83s |
Inserito il - 13/02/2006 : 13:33:39
si infatti....boh...vedremo, cmq non ha senso fare un lab ad Aprile, poi uno a giugno... |
| iperattivo |
Inserito il - 13/02/2006 : 13:13:06
andate dai prof, però a dir la verità quando andai io a chiedere a loro un mese fa, mi dissero che il lab valeva fino a febbraio... |
| francesca |
Inserito il - 13/02/2006 : 12:26:00
Citazione:
Messaggio inserito da gym83s
mmm secondo me cmq vale fino ad Aprile...non avrebbe senso dato che la sessione è la stessa....
potete chiedere meglio???magari proprio a semmy???
 forse quest'anno si perche' c'e' l'appello di aprile!
(ad aprile la sessione non è la stessa, non è straordinaria?)
GLi altri anni era fino a febbraio. cosi' è scritto sul sito di Semeraro. |
| gym83s |
Inserito il - 13/02/2006 : 11:24:29
mmm secondo me cmq vale fino ad Aprile...non avrebbe senso dato che la sessione è la stessa....
potete chiedere meglio???magari proprio a semmy??? |
| francesca |
Inserito il - 11/02/2006 : 16:28:45
La prova di LAB in qualunque appello venga superata, ha validita' fino a febbraio! |
| francesca |
Inserito il - 11/02/2006 : 16:25:47
mmmm 
mi sa che Semeraro lo specifica sul sito....
vado leggo e torno! |
| shummenda |
Inserito il - 11/02/2006 : 16:11:25
sapete che vi dico? mi sono rotto la minchia e il 14 non lo provo nenche. anche perchè è sabato e ho scordato di prenotare l'esame ieri(che dovrebbe essere stato l'ultimo giorno utile). quindi colgo l'occasione per salutare i soliti (massimo e quell'altro michele) sperando per voi di non trovarvi ad aprile!! solo una cosa: ma sto caz-zo di laboratorio lo conservano fino ad aprile o l'ultimo mese era febbraio. ditemi che è aprile ragà |
| gym83s |
Inserito il - 11/02/2006 : 12:02:36
quanti l'hanno passato? |
| iperattivo |
Inserito il - 10/02/2006 : 17:11:56
si si,proprio con il P.L.anche se adir dai voti mi sa che l'han fatto proprio in pochi... |
| Marketto |
Inserito il - 09/02/2006 : 20:11:18
Col pumping lemma per il linguaggi liberi..lo trovi sul libro! |
| gym83s |
Inserito il - 09/02/2006 : 19:34:21
si...era proprio quello...come si faceva?? |
| Marketto |
Inserito il - 09/02/2006 : 13:30:57
Non puoi dimostrarlo con la concatenazione, devi dimostrarlo con il pumping lemma per i linguaggi liberi. E' la traccia dell'ultimo appello, giusto? |
| confusa_e_felice |
Inserito il - 09/02/2006 : 13:10:07
1.1) Dimostrare formalmente che il linguaggio
L={a^j b^k c^k: 0<=j<=k} non è un linguaggio lineare destro.
supponiamo per assurdo che L sia regolare
allora esiste un automa M=(Q,delta,q0,F) tale che L=T(M)
supponiamo che |Q|=n con n>0
consideriamo la parola
a^n b^n c^n (j=k =n)
aa...abb...bcc...c
l'automa M parte da qo legge le n a e si porta in q, poi legge le n b e si porta in q1. Di seguito legge la prima c e si porta in q2,legge la seconda c e si porta in q3, legge la n-esima c e si porta in qn+1 in cui M transita.
poichè M ha solo n stati due tra gli stati q1,q2,...,qn+1 devono coincidere
siano qi e qj tali che qi=qj=q ,i<j
nel grafo degli stati di M esiste dunque un ciclo di lunghezza j-i.
l'esistenza di questo ciclo nel grafo M ci permette di aggiungere altre c nella parola di ingresso, ottenendo ancora parole accettate da M se il numero di c aggiunte è un multiplo di j-i. dunque anche a^n b^n c^n+k(j-i) appartiene a T(M). siamo dunque giunti ad una contraddizione.
a^n b^n c^n+k(j-i) appartiene a T(M) ma non appartiene ad L
ora stabilire se L è libero da contesto
L=L1*L2(*concatenazione)
L1=(a^j) j>=0
L2=(b^kc^k) k>=0
due linguaggi liberi da contesto e quindi anche la loro concatenazione
ma come faccio ad introdurre j<=k? ho sbagliato a dividere così il linguaggio?
qualcuno potrebbe aiutarmi e magari dirmi se ho sbagliato? grazie |
| dearnet |
Inserito il - 28/01/2006 : 14:20:47
Ciao raga i risultati ci sono?? e dove??? |
| Marketto |
Inserito il - 27/01/2006 : 09:47:17
Allora..il secondo esercizio era un automa con 4 stati (q0,q1,q2,q3), con q3 finale. Da uno stato all'altro potevano passare 0,1 o 2. Infine c'era una transizione da q3 a q2 passandogli 0,1 o 2. Io l'ho fatto così e poi gli ho fatto la tabella di transizione. |
| gym83s |
Inserito il - 26/01/2006 : 23:07:29
ok ok! Cerca e vedrai che troverai..!!
|
| MAX_83 |
Inserito il - 26/01/2006 : 19:51:21
ue michele sono massimo ho mandato una email al prof ferilli per sapere i risultati del laboratorio mi ha risposto dicendo che si trovanno in qualche sito di un professore che risposta! ci vediamo lunedi |
| gym83s |
Inserito il - 26/01/2006 : 17:09:52
in effetti c'è un piccolo errore sull'esercizio 2, è come dici tu Marketto, ma io volevo sapere...come sono stati fatti oltre ai metodi usati..perchè per
il numero 1.1 penso di aver fatto bene
il numero 1.2 non sono sicuro
il numero 2 buio totale (come viene l'automa??)
 |
| gym83s |
Inserito il - 26/01/2006 : 15:57:51
Avevo capito caro Marketto...intendevo dire....COME???
tu lo hai fatto?? |
| Marketto |
Inserito il - 26/01/2006 : 15:55:02
Citazione:
Messaggio inserito da gym83s
Ciao Ragazzi, questo è il consueto appuntamento post-esame dove come al solito si chiariscono gli esercizi......
peccato però che sia ancora io a postare questo...
quando sarà il giorno che LINGUAGGI sarà MIO????mmah ad ogni modo le tracce di oggi erano:
1.1) Dimostrare formalmente che il linguaggio
L={a^j b^k c^k: 0<=j<=k} non è un linguaggio lineare destro.
(Se non sbaglio si usa il Pumping Lemma per i linguaggi regolari..o no??)
1.2) Stabilire se L è libero da contesto.Dimostrare formalmente la risposta. (come si faceva?? Il pumping Lemma c.f.??non riesco a capirlo...)
2) Progettare, commentando opportunamente l'automa riconoscitore a stati finiti per il seguente linguaggio:
L={w e {0,1,2}* : |w| =2k+1, k>0}
(e questo??? chi l'ha fatto?? Io no.........)
Se qualcuno ha svolto qualcuno degli esercizi risponda please......
CIAOOOO
Per la prima parte del primo esercizio si utilizzava il P.L. per i linguaggi regolari, per la seconda parte le operazioni sui linguaggi (cioè dovevi dividere il linguaggio in due parti e poi fare la concatenazione ecc..).
Il secondo esercizio si faceva costruendoti l'automa e disegnando la tabella di transizione. A me la traccia diceva di costruire la tabella di transizione, non di progettare commentando opportunamente. |
