Důkaz
p
umping
l
emm
y
1/3
•
Nechť
L
je
libovolný regulární jazyk
.
Potom
existuje
D
K
A
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
sta
vů
:
s
a
1
a
2
…
a
n
|
–
q
1
a
2
…
a
n
|
–
…
|
–
q
n
-1
a
n
|
–
q
n
|
z
|
|
z
|
+
1
sta
vů
q
1
s
q
n
a
1
a
2
…
q
n
-1
a
n
•
pro
z
=
a
1
a
2
...
a
n
:
a
n
-1
4
/26