Let | |
,
.
vx m m n
=
≤
By Pumping Lemma, uv wx y
2
2 is in L.
Since
|
|
,
|
|
.
uv wx y n
uv wx y k
2
2
2
2
2
2
>
=
where k n
≥ +1.
But |
|
.
uv wx y n
m n
n
2
2
2
2
2 1
=
+ <
+ +
Therefore, |
|
uv wx y
2
2 lies between n
2 and (n + 1)
2 .
Hence, uv wx y L
2
2
∉ , which is a contradiction.
Therefore, {
:
}
a
n
n
2
1
≥ is not context-free.
3.4 DECISION ALGORITHMS
THE O REM: Given L is a regular set, i.e., a language accepted by a finite
automaton. There exists a constant ‘n’ such that if ‘s’ in any string in L and
| | ,
s n
≥ then s uvw
=
such that | | ,
uv n
≤ | |
v ≥1 and for all i
uv w L
i
≥
∈
0,
.
Proof: Let us assume that L = T(M) where M
Q
q F
= ( , , , , )
Σ δ 0
and ‘n’ be the
number of states in Q.
Let
w a a
a
L
m
=
∈
1 2 KK
where m c
≥
and
δ( , , ,
)
.
q q q
a
q
i
i
0
1
2 KK
=
Since m n
≥ , the number of states, the sequences q q
q m
0
1
, , KK
will have
some repeated states.
Hence there are two integers j and k, 0 ≤ < <
j k n such that q i = q k .
Let us assume that k is least in the chosen pair (j, k).
For this we have
(a) q i = q k
(b) if 0 < 1< k, then q q
i
j
≠
for all 0
1
≤ <
i , therefore q q
q k
0
1
1
, , KK −
are distinct states in Q and k n
≤ .
Let u a a
a v a
a
j
j
k
=
= +
1 2
1
KK
KK
;
,
and w a
a
k
n
= +1,
,
KK
.
Therefore s = uvw (as shown in Fig.).
Since δ
δ
( , )
, ( , )
.
q v q
q
q v
q
i
k
j
j
i
j
=
=
=
Therefore δ( ,
)
.
q uv w q
F
i
m
0
=
∈
176
Theory of Automata, Formal Languages and Computation
q 0
q= q
i
k
q m
a, .... a
j+k 1
a
.... a
1
j
a 2
a, .... a
k+m 1