Pumping Lemma: Application II
.
1/3
•
We can use the pumping lemma to prove
some other theorems.
Illustration:
•
Let
M
be a DFA and
k
be
the
pumping lemma
const
ant
(
k
is the
number of states in
M
). Then
,
L
(
M
) is infinite
Û
there
exists
z
Î
L
(
M
),
k
£
|
z
|
<
2
k
Proof:
1)
there exists
z
Î
L
(
M
)
,
k
£
|
z
|
<
2
k
Þ
L
(
M
)
is
infinite
:
if
z
Î
L
(
M
)
,
k
£
|
z
|
, then by PL:
z = uvw
,
v
¹
e
, and for each
m
³
0:
uv
m
w
Î
L
(
M
)
L
(
M
) is infinite
10/26