Důkaz pumping lemmy 3/3
•  Obecně tedy M může provést přechody:
• pro m = 0, uvmw = uv0w = uw,
1.
2.
3.
suw
|–i qw
|–* f,  f Î F
1.
3.
• pro každé m > 0,
suvmw
|–i  qvmw
|–* f,  f Î F
1.
3.
|– j qvm-1w
2.
|– j qw
|– j ...
2.
2.
Celkově:
1) qv |– j q, j ³ 1; proto |v| ³ 1, tedy v ¹ e
2) suv |–i qv |– j q, i + j £ k; proto |uv| £ k
3) Pro každé m ³ 0: suvmw |–* f,  f Î F, proto uvmw Î L
                                                                                CBD
su |–i q;        qv |– j q;      qw |–* f, f Î F, tedy:
6/26