Důkaz
p
umping
l
emm
y
2/3
•
Nechť
k
= card
(
Q
)
(
celkový počet stavů v
M
).
Pro každé
z
Î
L
a
|
z
|
³
k
,
M
navštíví nejméně
k +
1 st
avů
.
Protože
k +
1
>
card
(
Q
)
,
musí
existovat stav
q
, který
M
navštíví nejméně dvakrát
.
s
z
=
s
u
v
w
|
–
i
q
v
w
|
–
j
q
w
|
–
*
f
,
f
Î
F
Celkově:
•
Pro
z
existuje
u
,
v
,
w
takové, že:
z
=
u
v
w
:
s
čtení
v
q
čtení
u
f
čtení
w
s
u
|
–
i
q
q
w
|
–
*
f
q
v
|
–
j
q
;
j
³
1
,
i + j
£
k
5
/26