Qualcuno sa rispondere alla mia domanda?
Allora...
Io ho il linguaggio L = {a^i b^n a^j b^n a^k : i,j,k>=0 e n>0}.
Voglio dimostrare ke L é non regolare attraverso la proprietà di chiusura dei linguaggi regolari, e x far questo devo utilizzare il linguaggio {b^n c^n : n>0} ke so già non regolare.
Il mio ragionamento é: assumo x assurdo ke L sia regolare.
L'unione tra L e {b^n c^n : n>0} (poiché tale linguaggio é semplicemente un caso particolare di L) é proprio L stesso.
Ma io so ke i linguaggi regolari sono chiusi rispetto all'unione.
Quindi l'unione tra un linguaggio regolare (L, x ipotesi)ed uno non regolare darà come risultato un linguaggio non regolare.
Quindi L, il linguaggio risultante, é non regolare.
Ma noi l'avevamo supposto regolare: da ciò l'assurdo!
Quindi abbiamo dimostrato la non regolarità di L.
E' giusto questo mio ragionamento?
Ossia: la proprietà di chiusura su una certa operazione ("se i 2 termini sono regolari allora il risultato é regolare"), si può anke interpretare come "se uno dei 2 termini é non regolare allora il risultato é non regolare"?
Ringrazio vivamente chiunque sia in grado di rispondere!
|
Proprietà di chiusura!
Inserito il - 21/06/2005 : 00:08:52
