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