Problem Solving in Automata, Languages, and Complexity

144 CONTEXT-FREE LANGUAGES

T2

$2

V Y

T3

X

Figure 3.19: Proof of the pumping lemma.

this longest path plus the ancestors of qi would form a path longer than n).

Therefore, IKMJ~ < d”+’ = Ii’.

(3) For n = ~,~&xx-J~Z is just w E L(G). For n = 0, we can obtain a parse

tree T’ for uv”2yoz = uxz as described in part (1) above. For n > 2, we obtain

a parse tree for uwnxynz by inserting n - 1 extra copies of subtree T2 between

the original subtrees T2 and T3 (see Figure 3.19(c)). So, uvnxy’? E L(G) for

all n 2 0.^0

Example 3.44 Show that { anbncn 1 n > - 0) is not a context-free language.

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

by a context-free grammar G. Let li’ be the constant associated with G, as

given in Lemma 3.43. Consider string w = aKbK cK. By Lemma 3.43, w can

be decomposed as w = uwxyx, satisfying conditions (l)-(3) of Lemma 3.43.

By condition (2) wxy is either a substring of aKbK or a substring of bKcK.

If vxy is a substring of a K b K then, by condition (1) the string uxz has either

less than K occurrences of a or less than K occurrences of b. However, since

‘uxy is a substring of aKbK , we know that cK is a substring of z and so

uxx has K occurrences of symbol c. It follows that uxx @ L, contradicting

condition (3). S imilarly, we can also get a contradiction in the case that vxy

is a substring of b K c K. Thus, L cannot be context-free.^0

Example 3.45 Show that L = {ww 1 w E (0, l}*} is not a context-free

language.