Pumping Lemma: Aplikace II. 2/3
2) L(M) je nekonečný Þ existuje z Î L(M), k £ |z| < 2k:
Předpokládme, že L(M) je nekonečný a neexistuje z Î L(M), |z| ³ k
a) Dokážeme sporem, že:
• L(M) je nekonečný Þ existuje z Î L(M),
|z|
³ k
• Dokážeme sporem, že platí:
L(M) je nekonečný
existuje z Î L(M), |z| ³ k
existuje z Î L(M), k
£ |z| < 2k
a)
b)
pro všechna z Î L(M) platí: |z| < k
L(M) je konečný
Spor!
11/26