.dsy:it. - Help pumping lemma

.dsy:it.
//www.dsy.it

Help pumping lemma

Posted by mattiie on 14-04-2011 12:31

Pumping lemma:
"Sia L un linguaggio regolare. Esiste allora una costante N tale che, per ogni stringa w in L per la quale |w|>=N, possiamo scomporre w in tre stringhe w= xyz in modo che
(1) y diverso da epsilon (stringa vuota)
(2) |xy| <= N
(3) per ogni k >= 0 anche la stringa x y^k z è il L"

Questo teorema sembra non funzionare per il linguaggio regolare L="numero pari di a" in alfabeto {a,b}
infatti prendendo una stringa a caso w=aabaa
e dividendola in
x=a
y=a
z=baa
abbiamo le prime 2 condizioni verificate ma la terza no!
infatti per k=2 abbiamo la stringa aaabaa che viene accettata nonostante non abbia un numero pari di a.

Chi mi aiuta a trovare l'errore nel mio ragionamento??