Proof of Pumping Lemma 3/3
•  There exist moves:
• for m = 0, uvmw = uv0w = uw,
1.
2.
3.
suw
|–i qw
|–* f,  f Î F
1.
3.
• for each m > 0,
suvmw
|–i  qvmw
|–* f,  f Î F
1.
3.
|– j qvm-1w
2.
|– j qw
|– j ...
2.
2.
Summary:
1) qv |– j q, j ³ 1; therefore, |v| ³ 1, so v ¹ e
2) suv |–i qv |– j q, i + j £ k; therefore, |uv| £ k
3) For each m ³ 0: suvmw |–* f,  f Î F, therefore uvmw Î L
                                                                                QED
su |–i q;        qv |– j q;      qw |–* f, f Î F, so
6/26