| Autore |
 Discussione  |
|
|
pinux
Utente Mamone
Regione: Puglia
|
 Inserito il - 09/06/2005 : 19:58:16
|
ho svolto il seguente esercizio, quanlcuno mi sa dire se è corretto? 
dato il seguente linguaggio
L={a^i b^j c^k : k=i+j, i,j,k>=0}
dimostrare che nn è regolare
allora...
supponiamo per assurdo che L sia regolare.
Quindi esiste M=(Q,d,q0,F) => T(M)=L
supponiamo che |Q|=n con n>0
considero la seguente sottostringa
c^n
della parola di L
a^n-1 b c^n
M si trova nello stato q1, quindi legge la prima c e si porta in q2 fino a leggere la n-esima c portandosi nello stato qn+1
Abbiamo quindi n+1 stati in cui M transita. Poichè M ha solo n stati, due tra q1...qn+1 devono coincidere
Supponiamo che siano q^i e q^j tali stati
q^i = q^j = q i<j
esiste dunque un ciclo di lunghezza j-i nel grafo degli stati di M
tale ciclo ci permette di aggiungere altre c se il suo numero è multiplo di j-i.
dunque otteniamo:
a^n-1 b c^n+k(j-i) che appartiene a T(M)
ma se k>0 verifichiamo che a^n-1 b c^n+k(j-i) non appartiene a T(M)
Da cui l'assuro. Quindi L non è regolare
|
|
|
|
pinux
Utente Mamone
Regione: Puglia
|
 Inserito il - 09/06/2005 : 20:04:11
|
oppure dovrei considerare la sottostringa
a^n
della parola di L
a^n b c^n+1
M si trova nello stato q1, quindi legge la prima a e si porta in q2 fino a leggere la n-esima a portandosi nello stato qn+1
Abbiamo quindi n+1 stati in cui M transita. Poichè M ha solo n stati, due tra q1...qn+1 devono coincidere
Supponiamo che siano q^i e q^j tali stati
q^i = q^j = q i<j
esiste dunque un ciclo di lunghezza j-i nel grafo degli stati di M
tale ciclo ci permette di aggiungere altre c se il suo numero è multiplo di j-i.
dunque otteniamo:
a^n+k(j-i) b c^n+1 che appartiene a T(M)
ma se k>0 verifichiamo che a^n+k(j-i) b c^n+1 non appartiene ad L
Da cui l'assuro. Quindi L non è regolare |
|
Modificato da - pinux in data |
 |
|
|
pinux
Utente Mamone
Regione: Puglia
|
Inserito il - 09/06/2005 : 20:17:49
|
| oppure vanno bene entrambi le soluzioni?? |
|
|
|
|
Pavel4
Utente giovane
Regione: Puglia
Prov.: Bari
Città: Palo del Colle
|
Inserito il - 07/07/2005 : 15:22:37
|
Citazione:
Messaggio inserito da pinux
oppure vanno bene entrambi le soluzioni??
up... qualcuno potrebbe rispondere ??
ciao
grazie |
it's like an angel fly
it's like a dream
|
|
|
|
falco_85
Utente giovane
Regione: Puglia
Prov.: Bari
|
Inserito il - 07/07/2005 : 21:56:54
|
| Secondo me vanno bene tutte e due |
|
|
|
DarkSiDe
Utente medio
Regione: Puglia
Prov.: Bari
|
Inserito il - 07/07/2005 : 22:18:44
|
| ho letto molto velocemente e per quel che ricordo, credo vadano bene ma secondo me ti trovi meglio a considerare a^n b^n c^2n ;) |
"mai discutere con un idiota...ti trascina al suo livello e ti batte con l'esperienza" |
|
|
|
DarkSiDe
Utente medio
Regione: Puglia
Prov.: Bari
|
Inserito il - 07/07/2005 : 22:20:28
|
| cmq dubito uscirà nuovamente il PL per i linguaggi regolari, almeno per il momento |
"mai discutere con un idiota...ti trascina al suo livello e ti batte con l'esperienza" |
|
|
|
pinux
Utente Mamone
Regione: Puglia
|
Inserito il - 08/07/2005 : 11:59:23
|
Citazione:
Messaggio inserito da DarkSiDe
ho letto molto velocemente e per quel che ricordo, credo vadano bene ma secondo me ti trovi meglio a considerare a^n b^n c^2n ;)
ho questo semplice dubbio:
se considero la stringa a^n b^n c^2n
devo semplicemente prendere una qualsiasi sottostringa che dimostri che pompandola nn rispetta il Pumping lemma? oppure devo prendere tutte le sottostringhe e analizzarle una ad una?
grazie ;-) |
|
|
|
| |
Discussione |
|
Pumping lemma... è corretto?
