| Autore |
 Discussione  |
|
oracolo
Nuovo Utente
|
 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...
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 25/06/2004 : 20:57:25
|
Hai provato con il pumping lemma per i linguaggi regolari, considerato che il numero di a e di b è vincolato?
P.S. la traccia non è chiarissima. ma immagino che sia i,j>=0, i<=j<=3n
Confermi? |
 |
|
|
oracolo
Nuovo Utente
|
Inserito il - 25/06/2004 : 21:39:30
|
si professore, avendola incollata da word, dove ci stavo lavorando, non mi ha preso certi caratteri.
grazie mille, provo e la tengo aggiornata, magari se mi serve qualche suggerimento, la importuno ancora |
|
|
|
oracolo
Nuovo Utente
|
Inserito il - 25/06/2004 : 21:44:03
|
senta vorrei porle un altra domanda visto che è stato cosi gentile,
come esercizio di riferimento x svolgere il suddetto, ho preso quello del libro di Semeraro a pagina 198, n. 7.9
Che ne pensa va bene come base da cui partire.
Grazie |
|
|
|
oracolo
Nuovo Utente
|
Inserito il - 25/06/2004 : 21:46:03
|
riscrivo la traccia x maggiore chiarezza, x tutti
L = { a(elevato) i b(elevato) j / i,j>=0, i<=j<=3n } |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 25/06/2004 : 21:57:28
|
cosa intendi con "base da cui partire"?
Credo che qualunque esercizio vada bene per iniziare. Ma per il tuo esrcizio specifico, devi crcare di individuare innanzitutto quale z usare per il pumping lemma, e poi basandoti sui vincoli del linguaggio, trovare i casi in cui, per effetto del ciclo tra gli stati dell'automa, si ottiene unaparola che viola questi vincoli |
|
|
|
oracolo
Nuovo Utente
|
Inserito il - 25/06/2004 : 22:45:26
|
appunto questo è il problema, come scegliere z???
La X=[a,b]
scegliere z se non erro significa considerare sottosrtinghe tipo a(elevato)1 b(elevato)2, a(elevato)2 b..... , ........ |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 25/06/2004 : 23:10:18
|
Citazione:
Messaggio inserito da oracolo
La X=[a,b]
Che significa?
Citazione:
scegliere z se non erro significa considerare sottosrtinghe tipo a(elevato)1 b(elevato)2, a(elevato)2 b..... , ........
No, significa scegliere una parola del linguaggio la cui lunghezza sia maggiore del numero di stati fissato per l'automa.
Hai letto l'enunciato del pumping lemma? C'e' scritto li.
Poi, nel corso della applicazione del pumping lemma, la z viene ppompata o depompata a seconda del caso |
|
|
|
Chilavert
admin
Regione: Puglia
Prov.: BA
Città: Bari
|
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
|
E' un bene per il Prof. Xxxxxxx che sappia con chi ha a che fare.
Pensa a studiare e non agli esempi, o ad altre strade per così dire,
che questa volta mi sa che non attacca. [cit.]
Tutti professori dall'esterno, e poi parlano persone che per prendere un voto decente
ripetono l'esame 30 volte e poi fanno i sapientoni con chi segue la prima volta vedi chilavert [cit.] |
|
|
|
oracolo
Nuovo Utente
|
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? |
|
|
|
oracolo
Nuovo Utente
|
Inserito il - 26/06/2004 : 01:01:18
|
| chila è la traccia di semeraro questa, l'ultima. |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
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. |
|
|
|
Chilavert
admin
Regione: Puglia
Prov.: BA
Città: Bari
|
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 |
E' un bene per il Prof. Xxxxxxx che sappia con chi ha a che fare.
Pensa a studiare e non agli esempi, o ad altre strade per così dire,
che questa volta mi sa che non attacca. [cit.]
Tutti professori dall'esterno, e poi parlano persone che per prendere un voto decente
ripetono l'esame 30 volte e poi fanno i sapientoni con chi segue la prima volta vedi chilavert [cit.] |
|
|
|
oracolo
Nuovo Utente
|
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.
|
|
|
|
Sinkler
Croce & Delizia
Regione: Puglia
Prov.: Bari
Città: Molfetta
|
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
Nuovo Utente
|
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
Croce & Delizia
Regione: Puglia
Prov.: Bari
Città: Molfetta
|
Inserito il - 27/06/2004 : 20:53:14
|
allora Teorema di Kleene(pag.165)
L3=Lreg |
|
|
|
fabbattista
utente SEMPRE giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
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.
|
|
|
|
Chilavert
admin
Regione: Puglia
Prov.: BA
Città: Bari
|
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 |
E' un bene per il Prof. Xxxxxxx che sappia con chi ha a che fare.
Pensa a studiare e non agli esempi, o ad altre strade per così dire,
che questa volta mi sa che non attacca. [cit.]
Tutti professori dall'esterno, e poi parlano persone che per prendere un voto decente
ripetono l'esame 30 volte e poi fanno i sapientoni con chi segue la prima volta vedi chilavert [cit.] |
|
|
|
oracolo
Nuovo Utente
|
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. |
|
|
|
lckw
Nuovo Utente
|
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.
|
|
|
|
Discussione |
|
|
|
chiedo aiuto
