Pumping Lemma: Application II. 3/3
If z0 Î L(M) and |z0| ³ k, the PL implies:  z0 = uvw, |uv| £ k, and for each m ³ 0, uvmw Î L(M)
b) Prove by contradiction
Contradiction !
Assume that there is z Î L(M), |z| ³ k
k
2k
|uw| = |z0| – |v|
for m = 0: uvmw = uw Î L(M)
Summary: uw Î L(M), |uw| ³ k and |uw| < |z0|!
z0 is not the shortest string satisfying z0 Î L(M), |z0| ³ k
³ 2k
£ k
Let z0 be the shortest string satisfying  z0 Î L(M), |z0| ³ k
Because there exists no z Î L(M), k £ |z| < 2k, so |z0| ³ 2k
and there is no z Î L(M), k £ |z| < 2k
³ k
there exists z Î L(M), k £ |z| < 2k
• there exists z Î L(M), |z| ³ k Þ
12/26