Pumping
l
emma: Apli
k
a
ce
II
.
1/3
•
Pumping lemmu je možné použít k dokazování
dalších tvrzení.
Ilustra
ce
:
•
Nechť
M
je DKA a
k
konstanta z pumping
lemmy (
k
je
počet stavů v
M
). Potom platí:
L
(
M
) je nekonečný
Û
existuje
z
Î
L
(
M
),
k
£
|
z
|
<
2
k
Důkaz:
1)
existuje
z
Î
L
(
M
)
,
k
£
|
z
|
<
2
k
Þ
L
(
M
)
je nekonečný
:
pokud
z
Î
L
(
M
)
,
k
£
|
z
|
,
potom podle
PL:
z = uvw
,
v
¹
e
a d
á
le
pro každé
m
³
0:
uv
m
w
Î
L
(
M
)
L
(
M
) je nekonečný
10/26