Pumping Lemma: Application II. 2/3
2) L(M) is infinite Þ there exists z Î L(M), k £ |z| < 2k:
 Assume that L(M) is infinite and there exists no z Î L(M), |z| ³ k
a) Prove by contradiction that
• L(M) is infinite Þ there exists z Î L(M), |z| ³ k
• We prove by contradiction, that
L(M) is infinite
there exists z Î L(M), |z| ³ k
there exists z Î L(M), k £ |z| < 2k
a)
b)
for all z Î L(M) holds  |z| < k
 L(M) is finite
Contradiction !
11/26