148 CONTEXT-FREE LANGUAGES
We can prove by induction that if every path of a parse tree T contains at
most i marked internal nodes, then T has at most di marked leaves. First,
assume i = 0; that is, assume that all internal nodes of T are unmarked.
Then, there must be at most do = 1 marked leaf, for otherwise the lowest
ancestor of any two marked leaves must be marked.
Next, consider the case i > 1. Let q be a marked internal node in T whose
proper ancestors are all unmarked. Then, we can see that all marked leaves
in T are descendants of q, for otherwise the lowest ancestor p of both q and
any marked leaf T which is not a descendant of q would be a marked internal
node (see Figure 3.20(b)). W e o b serve that q has at most d children, each of
which is the root of a subtree with at most i - 1 marked internal nodes in
any path. So, by the inductive hypothesis, each of these subtrees has at most
d ‘-l marked leaves, and so there are totally at most di marked leaves in T.
This completes the induction proof.
Now, since w has at least I< - - d”+’ marked symbols, the maximum num-
ber of marked internal nodes in a path of T is > nz + 1. Thus, such a path
contains at least one pair of marked internal nodes with the same label. Let
us choose a path 7r with the maximum number of marked internal nodes, and
choose its lowest pair of marked nodes (ql,qz) with the same label. Then,
we decompose tree T into subtrees Tl, T2 and T3, at these two nodes, as in
Lemma 3.43. The corresponding decomposition of the leaves w into uvxyx
satisfies conditions (l)-(3). W e 1 eave the details to the reader.^0
Example 3.52 Show that L = { unbnci 1 i # n} is not context-free.
Proof. To prove this result by Lemma 3.43, we might start with the string
W = uKbK~K+K! so that if v - - uj and y = bj, then j < I< and, so, we get
a contradiction when we “pump” v and y for K!/j time; The problem with
this approach is that it fails in the case when vzy = cj for some j > 0. To
avoid this problem, we might use Ogden’s lemma and mark all letters a in w
to force the case of v = uj and y = bj. The detail is as follows:
Suppose, to the contrary, that there is a context-free grammar G generating
L. Let K be the constant associated with this grammar G, as given in Ogden’s
lemma. Consider string w = uKbK~K+K! with all symbols a marked. Then,
w can be decomposed as w = uvxyz satisfying conditions (l)-( 3) of Ogden’s
lemma.
First, we observe that neither v nor y contains more than one type of sym-
bols. For instance, if v contains both symbols a and b, then string uv2zy2z has
a symbol b occurring before a symbol a and, hence, is not in L, contradicting
condition (3).
By the above observation and condition (1) either b or c is not in vy.
Case 1. b is not in vy, Then, uv2xy2z has more u’s than b’s and, hence, is
not in L. This contradicts condition (3) e
Cuse 2. c is not in vy. Let j be the number of u’s in zly. Then, the string
uvnxyn, with n = I+ K!/j has as many u’s as c’s and, hence, is not in L.
Again, this is a contradiction.^0