Pumping Lemma: Aplikace II. 3/3
Pokud z0 Î L(M) a |z0| ³ k, PL zaručuje:  z0 = uvw, |uv| £ k a pro každé m ³ 0, uvmw Î L(M)
b) Dokážeme sporem:
       SPOR!      
Předpokl., že existuje z Î L(M), |z| ³ k
k
2k
|uw| = |z0| – |v|
pro m = 0: uvmw = uw Î L(M)
Celkově: uw Î L(M), |uw| ³ k a |uw| < |z0|!
z0 není nejkratší řetězec splňující z0 Î L(M), |z0| ³ k
³ 2k
£ k
Nechť z0 je nejkratší řetězec splňující z0 Î L(M), |z0| ³ k
Protože neexistuje z Î L(M), k £ |z| < 2k, musí:  |z0| ³ 2k
a neexistuje z Î L(M), k £ |z| < 2k
³ k
existuje z Î L(M), k £ |z| < 2k
• existuje z Î L(M), |z| ³ k Þ
12/26