Problem Solving in Automata, Languages, and Complexity

3.6 Pumping Lemmas for Context-Free Languages 145

Solution. Suppose, to the contrary, that L is a context-free language and G

is a context-free grammar generating L. Let 1< be the constant associated

with G, as given in Lemma 3.43. Consider string soul = OKIKOKIK (with

= OKIK). By Lemma 3.43, ulw can be decomposed as ww = uv~yx such

ZUhat conditions (l)-(3) of th e 1 emma are satisfied by this decomposition.

By condition (2), vzy is a substring of the first half of ww (OKIK), or a

substring of the middle 2K letters of w ( lKOK), or a substring of the second

half of ww (OKIK). I n each case, uzz contains a block of O’s (or l’s) that is

shorter than K, and a block of O’s (or l’s, respectively) of length exactly K.

It is obvious that such a string is not equal to w’w’ for any w’ E (0, l}*. This

contradicts condition (3) and, hence, proves that L is not context-free. cl

In Section 3.2, we have seen that sets like {Onlm 1 am. < ,&z} for some

positive constants cx and ,8 are context-free. When the inequ&ty am. < - ,8n is

changed to a nonlinear inequality, the set becomes non-context-free.

Example 3.46 Show that L = (0” 1” 1 m. < - n2} is not a context-free Zan-

guage.

Proof. Suppose, to the contrary, that there is a context-free grammar G that
generates L. Let Ii’ be the constant associated with G, as given in Lemma
3.43. Consider string w = Otlt2, where t = max{K, 2). By Lemma 3.43, w
can be decomposed as w = uwxyx, satisfying conditions (l)-(3) of the lemma.
We consider the following cases:
Case 1. vy contains at least one 0. Then, ux:x = Oilj, with i < t - 1 and
j > - t2 - K (by condition (2)). Since t = max{K, 2}, t2 - Ii’ > t”- 2t + 1 =
(t - 1)2. We see that j > i2 and so uxz $ L. This is a contradiction to
condition (3).
Case 2. vy = lj for some j, 1 < j < Ii’. Then, uv2xy2z = Otlt’+j $- L,
also contradicting condition (3). - -^0

Example 3.47 Show that L = {aibjck ] k = max{i, j} } is not a context-free

language.

Proof. Suppose, to the contrary, that L is a context-free language. Then, L
is generated by a context-free grammar G. Let li’ be the constant associated
with this grammar G, as given in Lemma 3.43. Consider string w = aKbKcK.
By Lemma 3.43, w can be decomposed as w = uz~xyx, satisfying conditions
(l)-(3) of the lemma.
By condition (2), we know that vxy cannot contain both a and c.
Case 1. my contains symbol c. In this case, the number of c’s in uxx is less
than Ii’ and the number of a’s in uxz is equal to K. Hence, uxz $ L, which
contradicts condition (3).
Case 2. vy does not contain symbol c. In this case, either the number of
a’s or the number of b’s in uv2xy2z is greater than K and the number of c’s
in uv2xy2z is equal to K. Hence, uv2xy2z $ L, again a contradiction. Cl