3.6 Pumping Lemmas for Context-Free Languages 151
Figure 3.21: Decomposition of the tree T.(2) There is a string wa, in I&, which has a parse tree Y” whose nonterminal
set is exactly VI, such that 4(wcy) = a.
(3) For each y E r, there is a nonterminal A, E VI and a (generalized)
parse tree 7+, with root A,, and a leaf A, such that the concatenation
of all other leaves is a string wy E Lo with $(w,) = y.
Proof of Claim. We prove the claim by induction on lull. For lull < K, this
is trivially true, with wa, = w and I? = 8. Assume that Iwl > I< and that T
is a parse tree for w, with the nonterminal set VI. Since lwl > li’ = dm2f1, a
longest path in T from the root to a leaf must have length at least m2 + 2.
Choose one of the longest paths 7r in T, and let 7r’ be its subpath of the
lowest m2 + 2 nodes, including the leaf. So, 7r’ has exactly m2 + 1 internal
nodes. Since there are at most m nonterminal symbols in VI, one of them
must occur in X’ for at least m + 1 times. We choose such a nonterminal A in
x’, and decompose tree T into m + 2 subtrees To, Tl,... , T,+l, at the m + 1
nodes whose labels are A (see Figure 3.21). (Note that all these subtrees are
nonempty.)
Let the nonterminal set of subtree Ti be Ui , for i = 0,... , nz+ 1. We observe
that at least one intermediate subtree Ti, 1 < - i < - nz, has the property that
m+l
Ui C - IJ Uj 9
j=O,j#i
for otherwise each Ui would contain a nonterminal Bi which is not in any other
subtree (and hence not equal to A), and the total number of nonterminals in