Information Technology Reference
In-Depth Information
more times to give other strings in the language. We use the notation
u
n
to mean the string
repeated
n
times and let
u
0
=
.
LEMMA
4.5.1
Let
L
be a regular language over the alphabet
Σ
recognized by a DFSM with
m
states. If
w
∈
L
and
|
w
|≥
m
, then there are strings
r
,
s
,and
t
with
|
s
|≥
|
rs
|≤
m
1
and
0
,
rs
n
t
is also in
L
.
Proof
Let
L
be recognized by the DFSM
M
with
m
states. Let
k
=
such that
w
=
rst
and for all integers
n
≥
m
be the length
of
w
in
L
.Let
q
0
,
q
1
,
q
2
,
...
,
q
k
denote the initial and
k
successive states that
M
enters after
receiving each of the letters in
w
. By the pigeonhole principle, some state
q
|
w
|≥
in the sequence
q
0
,
...
,
q
m
(
m
k
) is repeated. Let
q
i
=
q
j
=
q
for
i<j
.Let
r
=
w
1
...w
i
be the
string that takes
M
from
q
0
to
q
i
=
q
(this string may be empty) and let
s
=
w
i
+
1
...w
j
be the string that takes
M
from
q
i
=
q
≤
to
q
j
=
q
(this string is non-empty). It follows
m
. Finally, let
t
=
w
j
+
1
...w
k
be the string that takes
M
from
q
j
to
q
k
.Since
s
takes
M
from state
q
to state
q
, the final state entered by
M
isthesamewhether
s
is
deleted or repeated one or more times. (See Fig.
4.18
.) It follows that
rs
n
t
is in
L
for all
n
|
rs
|≤
that
≥
0.
0
p
1
p
As an application of the pumping lemma, consider the language
L
=
{
|
p
≥
}
.
We show that it is not regular. Assume it is regular and is recognized by a DFSM with
m
states. We show that a contradiction results. Since
L
is infinite, it contains a string
w
of length
k
=
2
p
1
m
. By Lemma
4.5.1
L
also contains
rs
n
t
,
n
≥
2
m
,thatis,with
p
≥
≥
0, where
p
.Thatis,
s
=
0
d
where
d
p
.Since
rs
n
t
=
0
p
+(
n−
1
)
d
1
p
w
=
rst
and
|
rs
|≤
m
≤
≤
for
0 and this is not of the form 0
p
1
p
n
≥
for
n
=
0and
n
≥
2, the language is not regular.
The pumping lemma allows us to derive specific conditions under which a language is
finite or infinite, as we now show.
LEMMA
4.5.2
Let
L
be a regular language recognized by a DFSM with
m
states.
L
is non-empty
if and only if it contains a string of length less than
m
. It is infinite if and only if it contains a string
of length at least
m
and at most
2
m
1
.
Proof
If
L
contains a string of length less than
m
, it is not empty. If it is not empty, let
w
be a shortest string in
L
.Thisstringmusthavelengthatmost
m
−
1 or we can apply the
pumping lemma to it and find another string of smaller length that is also in
L
.Butthis
would contradict the assumption that
w
is a shortest string in
L
.Thus,
L
contains a string
of length at most
m
−
1.
If
L
contains a string
w
of length
m
−
1, as shown in the proof of the
pumping lemma,
w
can be “pumped up” to produce an infinite set of strings. Suppose now
that
L
is infinite. Either it contains a string
w
of length
m
≤|
w
|≤
2
m
−
≤|
w
|≤
2
m
−
1 or it does not.
s
r
t
Start
q
q
0
q
f
Figure 4.18
Diagram illustrating the pumping lemma.
Search WWH ::
Custom Search