Problem Solving in Automata, Languages, and Complexity

154 CONTEXT-FREE LANGUAGES

case of v = E and y = bj with j # n - m2. Suppose that we start with a
string w = umbn, with n < m2. Then, we will have trouble with the case of
V = ui and y = bi. Using Ogden’s lemma does not seem to help much. In
the following, we show how to use Parikh’s lemma to force the pumping of a
substring of b” only.
Suppose, to the contrary, that L is context-free. Then, by Parikh’s lemma,
4(L) is a finite union of linear sets Tl ,... , Tk. Assume that, for each 1 < - i < - k,
Ti = ai+spuqg, f or some two-dimensional integer vector ~i and some finite
sets & of two-dimensional inte
B

er vectors. Note that the integers appearing

in the integer vectors in I’ = Uizl ({ai} U I’i) are nonnegative. Let do be the

maximum integer appearing in any integer vector in I’, and let d = max{ do, 3).

(Thus, for any (d+$ E I’, dl < d and d2 < d.)

Let m = d! and n = (d!)“= dl.. It i&ear that (m,n) E 4(L) and so

(m, n) E Ta for some i, 1 < i < k. We claim that IYi must contain a vector

(0, Y), with 1 < Y < d. Tosee this, let us assume that all vectors (p, q) in IYi

have p > - 1. STnce-(m, n) E Ti, we know that there are ml,... , me > 0 and

(Pl) Ql) 9 l l l 7 (pe, qe> E ri such that

b-b n> = ai + kmj(pj,q,)-

j=l

Since all pj’s are greater than 0, we see that CiX1 mj < m. It follows that

n < - (m+ l)d, since all integers qj and the second compon& of CQ are bounded

by d. However , since d - > 3, we know that

n= (d! 2 - d! > > (d + 2)d! - df = (d. + l)d! > d(d! + 1) = d(m + l),

and we have a contradiction. This completes the proof of the claim.
Now, since (0, r) E IYi, we know that (m, n) + t(0, Y) E z C 4(L) for all
t >O. - Fort= d!/r, we get (m,n + tr) = (d!, (d!)2) E 4(L>, which is a
contradiction. We conclude that L is not context-free.^0

• Example 3.59 Show that L = { upbg 1 gcd(p, q) = 1) is not context-free.

Proof. Suppose, to the contrary, that L is context-free. Then, by Parikh’s
lemma, c+(L) is a finite union of linear sets Tl ,... , Tk. Assume that, for each
l<i<k,T;= - - ai + span(b), f or some two-dimensional integer vector ai and
some finite sets I?i of two-dimensional integer vectors. Let d be the maximum
integer appearing in any integer vector in r = Ui=l({~~}~ri>. k NOW, let p be
a prime number such that p > 2d + 2. Note that we must have d > 1, and so
p > 4 and p + 1 < 2(p - 1). Consider the vector (p, q), where q = p+ (p - l)!.
It% clear that gcd(p, q) = 1 andso (p,q) ETA forsomei= l,..., k.
By the same argument as given in Example 3.58, we can prove that there
is a vector (0, r) in ri, with 1 < - r < - d, because

q = p+ (p - l)! > (p - l)(p - 2) > (p - 2)(p+ 1)/z > d(p+ - 1).