| V I S U A L I Z Z A D I S C U S S I O N E |
| pinux |
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
|
| 7 U L T I M E R I S P O S T E (in alto le più recenti) |
| pinux |
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 ;-) |
| DarkSiDe |
Inserito il - 07/07/2005 : 22:20:28
cmq dubito uscirà nuovamente il PL per i linguaggi regolari, almeno per il momento |
| DarkSiDe |
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 ;) |
| falco_85 |
Inserito il - 07/07/2005 : 21:56:54
Secondo me vanno bene tutte e due |
| Pavel4 |
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 |
| pinux |
Inserito il - 09/06/2005 : 20:17:49
oppure vanno bene entrambi le soluzioni?? |
| pinux |
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 |
