| Autore |
 Discussione  |
|
gym83s
Utente Estremo
Regione: Puglia
Prov.: Foggia
Città: Trinitapoli
|
 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
|
|
|
MAX_83
Utente giovane
Regione: Puglia
|
Inserito il - 26/01/2006 : 15:43:26
|
| RAGA MA I RISULTATI DI LABORATORIO PER IL CORSO A SONO STATI RESI NOTI? |
 |
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
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. |
Marco
Visitate il mio blog: http://www.cambridgetime.splinder.com |
Modificato da - Marketto in data |
|
|
|
gym83s
Utente Estremo
Regione: Puglia
Prov.: Foggia
Città: Trinitapoli
|
 Inserito il - 26/01/2006 : 15:57:51
|
Avevo capito caro Marketto...intendevo dire....COME???
tu lo hai fatto?? |
|
|
|
gym83s
Utente Estremo
Regione: Puglia
Prov.: Foggia
Città: Trinitapoli
|
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??)
 |
|
|
|
MAX_83
Utente giovane
Regione: Puglia
|
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
Utente Estremo
Regione: Puglia
Prov.: Foggia
Città: Trinitapoli
|
 Inserito il - 26/01/2006 : 23:07:29
|
ok ok! Cerca e vedrai che troverai..!!
|
|
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
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. |
Marco
Visitate il mio blog: http://www.cambridgetime.splinder.com |
|
|
|
dearnet
Nuovo Utente
Regione: Puglia
Prov.: Bari
Città: modugno
|
Inserito il - 28/01/2006 : 14:20:47
|
| Ciao raga i risultati ci sono?? e dove??? |
deaRnet |
|
|
|
confusa_e_felice
Nuovo Utente
|
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 |
|
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
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? |
Marco
Visitate il mio blog: http://www.cambridgetime.splinder.com |
|
|
|
gym83s
Utente Estremo
Regione: Puglia
Prov.: Foggia
Città: Trinitapoli
|
Inserito il - 09/02/2006 : 19:34:21
|
| si...era proprio quello...come si faceva?? |
|
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
|
|
iperattivo
Utente medio
Regione: Puglia
Prov.: Bari
Città: ba
|
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... |
ghjkl |
|
|
|
gym83s
Utente Estremo
Regione: Puglia
Prov.: Foggia
Città: Trinitapoli
|
Inserito il - 11/02/2006 : 12:02:36
|
| quanti l'hanno passato? |
|
|
|
shummenda
Nuovo Utente
Regione: Puglia
Prov.: Bari
Città: Conversano
|
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à |
|
|
|
francesca
Utente assiduo
Regione: Puglia
Prov.: Bari
Città: Bisceglie
|
Inserito il - 11/02/2006 : 16:25:47
|
mmmm 
mi sa che Semeraro lo specifica sul sito....
vado leggo e torno! |
|
|
|
francesca
Utente assiduo
Regione: Puglia
Prov.: Bari
Città: Bisceglie
|
Inserito il - 11/02/2006 : 16:28:45
|
| La prova di LAB in qualunque appello venga superata, ha validita' fino a febbraio! |
|
|
|
gym83s
Utente Estremo
Regione: Puglia
Prov.: Foggia
Città: Trinitapoli
|
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
Utente assiduo
Regione: Puglia
Prov.: Bari
Città: Bisceglie
|
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. |
Modificato da - francesca in data |
|
|
|
Discussione |
|
ESAME DI OGGI 26 GENNAIO 2006
