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
qv
|– j q; j ³ 1,
i
+ j £ k
5/26