Důkaz pumping lemmy 2/3
• Nechť k = card(Q)  (celkový počet stavů v M).
Pro každé z Î L a |z| ³ k, M navštíví nejméně
k + 1 stavů. Protože k + 1 > card(Q), musí existovat stav q, který M navštíví nejméně dvakrát.
 sz = suvw |–i qvw |– j qw |–* f,  f Î F
Celkově:
• Pro z existuje u, v, w takové, že: z = uvw:
s
čtení v
q
čtení u
f
čtení w
su |–i q
qw |–* f
qv |– j q;  j ³ 1,
    i + j £ k
5/26