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