Proof of Pumping Lemma 2/3
• Let k = card(Q)  (the number of states).
For each z Î L and |z| ³ k, M visits k + 1 or more states. As k + 1 > card(Q), there exists a state q that M visits at least twice.
 sz = suvw |–i qvw |– j qw |–* f,  f Î F
Summary:
• For z exist u, v, w such that z = uvw:
s
reads v
q
reads u
f
reads w
su |–i q
qw |–* f
qv |– j q;  j ³ 1,
    i + j £ k
5/26