Problem Solving in Automata, Languages, and Complexity

3.6 Pumping Lemmas for Context-Free Languages 155

Therefore, we know that (p, q + tr) E Ta C 4(L) for all t > 0. Note that r <
d < p- 1. So, we can choose t = (p- l)((p- l)!)/q and ge< (p, q+tr) E 4(L).
However,

q+tr=p+(p-I)!+

(P - 1) l (P - v

l r

r

= p + (p - I)! l (I+ (p - 1)) = p(l + (p - I)!),

and so gcd(p, q + kr) = p > 1. This establishes a contradiction, and we

conclude that L is not context-free. q

Exercise 3.6

1. Prove the following variations of the pumping lemma for context-free
   languages: v

( ) a

(b)

( > C

(4

( > e

For any context-free language L, there exists a constant I< > 0

such that any string w in L with 1~1 > I{ can be decomposed into

w= UV~V~ZXJ~~~X, satisfying the following conditions:

(1) (VlV2~Y2Yl~ 5 1-c

(a> IVlYll > O,lV2Y21 > 0, and

(3) for any n 2 0, uv;“v~xwy~y~z E L.

For any context-free language L, there exists a constant K > 0

such that any string w in L with lull > I< can be decomposed into

W = uvxyz, satisfying the following conditions:

(1) lvxyl < IX-,

(2) I4 > 0, IYI > 0, and

(3) for any n 2 0, uvnxynz E L.

For any context-free language L and any k > 0, there exists a

constant K > 0 such that any string w in L with IwI > Ii’ can be

decomposed into w = uvxyx, satisfying the following conditions:

(1) IVYI > - k and

(2) for any n > 0, uvnxynz E L.

For any context-free language L and any k > 0, there exists a

constant K > 0 such that any string w in L with IwI > I< can be

decomposed into w = uvxyx, satisfying the following conditions:

(1) I4 > - k, IYI > - k, and

(2) for any n 2 0, uvnxynz E L.

For any context-free language L and any k > 0, there exists a

constant K > 0 such that any string w in L with IwI > li’ can be

decomposed into w = uvxyx, satisfying the following conditions:

(1) JvxyI < I<,

(2) Iv1 > Ic, - IYI > h and -