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
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
there exists z Î L(M), k £ |z|
< 2k
• there exists z Î L(M), |z|
³ k
Þ
12/26