| V I S U A L I Z Z A D I S C U S S I O N E |
| oracolo |
Inserito il - 25/06/2004 : 20:52:04
ragazzi chi mi aiuterebbe a risolvere il seguente esercizio.....
dimostrare formalmente che il linguaggio:
L = { a(elevato) i b(elevato) j / i,j ¡Ý 0 , i ¡Ü j ¡Ü 3n }
non ¨¨ lineare dx.
Grazie a tutti coloro che vogliano aiutarmi... |
| 20 U L T I M E R I S P O S T E (in alto le più recenti) |
| oracolo |
Inserito il - 27/06/2004 : 23:16:50
chila effetivamente, mi sono reso conto che è come dici tu |
| lckw |
Inserito il - 27/06/2004 : 23:03:17
grazie mille!
|
| fabbattista |
Inserito il - 27/06/2004 : 22:54:28
Citazione:
Messaggio inserito da lckw
ciao sinkler!
il riconoscimento delle parole chiave l'ho fatto separatamente dal riconoscimento degli identificatori tramite un serie di strcmp..tu che dici..va bene o va male?l'ho fatto simile al compilatore di tano presente nella sezione download..
Se stiamo parlando di tracce di laboratorio di linguaggi, allora va male. Usa il metodo dell'esercizio dove c'erano Go, GET e SET. |
| Chilavert |
Inserito il - 27/06/2004 : 22:33:14
Citazione:
Messaggio inserito da Sinkler
ma perchè la correzione?? non va bene come ho fatto io?
non riesco a capire!
allora, guardate questo grafico
per k = 0, non si entra mai nel ciclo... questo vuol dire che vengono saltati (j-i) stati... spero di essere stato chiaro...
da qui viene la correzione fatta prima |
| Sinkler |
Inserito il - 27/06/2004 : 22:14:34
forse dovresti chiedere a fabbattista e non a me!anzi + a Ferilli!
fosse per me andrebbe tutto bene!! |
| lckw |
Inserito il - 27/06/2004 : 22:08:13
ciao sinkler!
il riconoscimento delle parole chiave l'ho fatto separatamente dal riconoscimento degli identificatori tramite un serie di strcmp..tu che dici..va bene o va male?l'ho fatto simile al compilatore di tano presente nella sezione download.. |
| Sinkler |
Inserito il - 27/06/2004 : 21:55:39
ma perchè la correzione?? non va bene come ho fatto io?
non riesco a capire! |
| lckw |
Inserito il - 27/06/2004 : 21:50:31
buona sera,
volevo chiedere una cosa riguardo il laboratorio di domani....
lo scanner che ho fatto riconosce le stringhe ,i numeri ,i commenti;
per il riconoscimento di parole chiave,ho fatto cosi':
if(strcmp(tkn->name,"begin")==0 || strcmp(tkn->name,"Begin")==0
|| strcmp(tkn->name,"BEGIN")==0) tkn->cat=BEGIN;
per Lei ciò è corretto?Oppure devo procedere come per l'esempio in aula che implicava il riconoscimento degli identificatori GO,GET,SET?
NOTA:tkn->cat indica la categoria dell'identicatore risultante.
|
| oracolo |
Inserito il - 27/06/2004 : 21:39:32
grazie mille, siete stati tutti cosi gentili, questo forum è una meraviglia.
Seguiro il suo consiglio prof, a breve proporro un altro esercizio svolto da me, x vedere cosa ne pensate. |
| Chilavert |
Inserito il - 27/06/2004 : 21:29:14
Citazione:
Messaggio inserito da Sinkler
allora continuo io (correggetemi!)...
Poichè M ha solo n stati,due tra gli stati q0,q1,...,qn devono coincidere.
Siano,qi e qj gli stati coincidenti,abbiamo quindi qi=qj ,con i<j.
Nel grafo degli stati m esiste quindi un ciclo lungo j-i.Poichè esiste tale ciclo,possiamo aggiungere altre "a" nella parola in ingresso,ottenendo ancora parole accettate da M se il numero di "a" aggiunte è un multiplo di j-i.
quindi anche a^[n+k(j-i)]b^n appartiene a T(M) con K=0,1,...
Ma a^[n+k(j-i)]b^n non appartiene al linguaggio L poichè dalla traccia i<=j<=3i.
Ciò è assurdo,quindi L non è regolare.
 
allora, c'è da fare qualche piccola correzione
con k = 0: la parola è a^(n-(j-i))b^n, che è accettata
con k <> 0: va bene
"a^[n+k(j-i)]b^n appartiene a T(M) con K=0,1,..." non va bene
La corretta definizione è:
"a^[n-(j-i)]b^n appartiene a T(M) con K=0"
"a^[n+k(j-i)]b^n appartiene a T(M) con K=1,2,..."
ora va meglio |
| fabbattista |
Inserito il - 27/06/2004 : 21:01:12
Oracolo,
un consiglio: non ti far fare gli esercizi per intero perchè non ti serve per imparare. Sforzati di farli tu (e prima leggi un po' di teoria dal libro) e poi chiedi sul forum se qualcuno ritiene che sia fatto bene o meno.
|
| Sinkler |
Inserito il - 27/06/2004 : 20:53:14
allora Teorema di Kleene(pag.165)
L3=Lreg |
| oracolo |
Inserito il - 27/06/2004 : 20:41:12
grazie mille sinkler, quindi dimostrando che il linguaggio non è regolare, si dimostra anche che non è lineare dx in automatico? |
| Sinkler |
Inserito il - 27/06/2004 : 20:34:51
allora continuo io (correggetemi!)...
Poichè M ha solo n stati,due tra gli stati q0,q1,...,qn devono coincidere.
Siano,qi e qj gli stati coincidenti,abbiamo quindi qi=qj ,con i<j.
Nel grafo degli stati m esiste quindi un ciclo lungo j-i.Poichè esiste tale ciclo,possiamo aggiungere altre "a" nella parola in ingresso,ottenendo ancora parole accettate da M se il numero di "a" aggiunte è un multiplo di j-i.
quindi anche a^[n+k(j-i)]b^n appartiene a T(M) con K=0,1,...
Ma a^[n+k(j-i)]b^n non appartiene al linguaggio L poichè dalla traccia i<=j<=3i.
Ciò è assurdo,quindi L non è regolare.
|
| oracolo |
Inserito il - 27/06/2004 : 19:52:00
quindi riepilogando, dovrei prendere z=a^nb^n (oppure come consiglia chila a^pb^p) e dire che l'automa partendo dallo stato qo legge una a per volta fino a che dopo la n-esima volta si porta in qn. Quindi abbiamo n+1 stati q0,q1,....qn in cui M transita.
Poiche M ha solo n stati due tra gli stati, q0,q1,....qn devono coincidere, e dico che gli stati coincidenti siano, qi=qj , dove nel mio caso i<=j<=3n
come continuo da qui in poi, ho diversi dubbi, x piacere chiaritemeli.
grazie mille x l'attenzione concessami.
|
| Chilavert |
Inserito il - 26/06/2004 : 10:35:50
Citazione:
Messaggio inserito da oracolo
chila è la traccia di semeraro questa, l'ultima.
allora lo svolgimento è quello che ti ho postato |
| fabbattista |
Inserito il - 26/06/2004 : 09:30:18
Citazione:
Messaggio inserito da oracolo
si prof ho letto l'enunciato, quindi va presa |z|> n dove n sono gli stati dell'automa, quindi potrei prendere a(elevato)n e b(elevato)n come parola.quindi z=anbn
giusto?
si giusto. |
| oracolo |
Inserito il - 26/06/2004 : 01:01:18
chila è la traccia di semeraro questa, l'ultima. |
| oracolo |
Inserito il - 26/06/2004 : 00:56:31
si prof ho letto l'enunciato, quindi va presa |z|> n dove n sono gli stati dell'automa, quindi potrei prendere a(elevato)n e b(elevato)n come parola.quindi z=anbn
giusto? |
| Chilavert |
Inserito il - 25/06/2004 : 23:40:08
Citazione:
Messaggio inserito da oracolo
riscrivo la traccia x maggiore chiarezza, x tutti
L = { a(elevato) i b(elevato) j / i,j>=0, i<=j<=3n }
io invece penso che sia i<=j<=3i
perchè la n non ha senso di esistere...
...se è così come dico io, col pumping lemma per i linguaggi regolari, scegliendo a^pb^p come parola e aggiungendo qualche a, esci dal linguaggio e hai concluso
|
