Problem Solving in Automata, Languages, and Complexity

152 CONTEXT-FREE LANGUAGES

tree T would be more than m.. Let us fix this subtree Ti, and let T’ be the tree
T with subtree Ti removed (with the root of Ti and the root of Ti+l merged
into a single node). We let zuo be the concatenation of the leaves of T’. Also
let u11 be the concatenation of terminal leaves in Ti. We observe the following
properties:

(a) 4(w) = vqwo) + 4(w)*

(b) lull1 < - K. (If 1~11 > K, then Ti would have a path longer than r’, and

7r would not be a longest path in T).

(c) The nonterminal set of T’ is exactly VI.

Now., we consider the following two cases:

Case 1. IwrI > 0. Then, 1~101 < IwI. Let p = +(wr). By the inductive

hypothesis,

for some ar E +(Lo) and I? C
the Claim. Therefore, we have

$(Lo), which satisfy properties (2) and (3) of

with Q! E $(Lo) and I U {p} C I satisfying properties (2) and (3) of the
Claim. (Note that ,0 satisfies property (3).)
Case 2. lwll = 0. Then, T’ is a parse tree of w, with at least one node
smaller than T. We can repeat the above process on T’ and, after a finite
number of times, we must reach a case with lwrl > 0.
This completes the proof of the Claim.
Finally we show that the lemma follows from the Claim. Assume that
w E L and that T is a parse tree of w with the nonterminal set VI. From
the claim, we have 4(w) = a + &q, for some ct E t$(Lo) and I C q5(Lo),

satisfying conditions (2) and (3). All we need to prove is that -

Q + span(r) C 4(L). -

Let p = a + cjZ1 k mjyj, where 71,... , yk E I and rn.1,... , ?‘-& > 0. First,
by property (2), there is a string wcy E LO, satisfying 4( wcy) = a, which has
a parse tree Ta with the nonterminal set VI. Now, for each yj, 1 < j < k,
let Tj be the (generalized) parse tree satisfying (3) with respect t&yj,and
let Aj be the root of Tj. By condition (3)) Aj E VI, and so it occurs in tree
Tcy. For each j, 1 < j < k, we insert mj copies of tree Tj at the node Aj
(cf. Figure 3.19(c)).L e t - w’ be the concatenation of the leaves of the resulting
tree. Then,
k

j=l

So, p E 4(L). Th is completes the proof of the lemma. cl