Důkaz pumping lemmy 1/3
• Nechť L je libovolný regulární jazyk. Potom existuje DKA  M = (Q, S, R, s, F) a L = L(M).
• Pro z Î L(M), M provede |z| přechodů a M navštíví
|z| + 1 stavů:
 sa1a2…an |– q1a2…an |– … |– qn-1an |– qn
|z|
|z| + 1 stavů
q1
s
qn
a1
a2
…
qn-1
an
• pro z = a1a2 ...an:
an-1
4/26