184 J,;i Theory of Computer Science
As k ?: 2. at least one of the sons is an internal vertex. By the left-to-right
ordeling of leaves. a can be written as ala: ... am' where ai is obtained by
the concatenation of the labels of the leaves which are descendants of vertex
Vi' If Vi is an internal vertex, consider the subtree of T with Vi as its root. The
number of internal vertices of the subtree is less than k (as there are k internal
vertices in T and at least one of them, viz. its root, is not in the subtree). So
by induction hypothesis applied to the subtree, Xi ~ ai' If 1\ is not an internal
vertex. i.e. a leaf, then Xi = ai'
Using (6.1), we get
A ::::} XIX: ... XIII ~ a I X:X 3 ... XIII ... ~ aj a2 ••• cx,n = a,
i.e. A ~ ex. By the principle of induction. A ~ a whenever a is the yield
of an A-tree.
To prove the 'only if' part. let us assume that A ~ a. We have to
constmct an A-tree whose yield is a. We do this by induction on the number
of steps in A ~ a.
When A ::::} a, A -7 a is a production in P. If a = XIX: ... XIII' the
A-tree with yield a is constmcted and given as in Fig. 6.5. So there is basis
for induction. Assume the result for derivations in at most k steps. Let
A b (X: we can split this as A ::::} Xj ... XI/i k~ a. Now, A ::::} Xj XIII
implies A -7 XjX 2 .•. XIII is a production in P. In the derivation XjX:
XIII
k~ (X, either (i) Xi is not changed throughout the derivation, or (ii) Xi is
changed in some subsequent step. Let (Xi be the substring of a delived from Xi'
Then Xi ~ ai in (ii) and Xi = (Xi in (i). As G is context-free, in every step of
the delivation XIX: ... XIII ~ a, we replace a single variable by a string. As
aj, a: . ..., aI/I' account for all the symbols in a, we have a = ala2 ... a III'
A
Fig. 6.5 Derivation tree for one-step derivation.
We constmct the derivation tree with yield a as follows: As A -7 Xl' .. XIII
is in P. we constmct a tree with Tn leaves whose labels are Xj, ..., X IlI in the
left-to-light ordeling. This tree is given in Fig. 6.6. In (i) above, we leave the
vertex Vi as it is. In (ii). Xi ~ ai is less than k steps (as XI ... XI/I I/~ a). By
induction hypothesis there exists an Xi-tree T i with yield ai' We attach the tree
T i at the vertex Vi (i.e. Vi is the root of T;). The resulting tree is given in
Fig. 6.7. In this figure. let i and j be the first and the last indexes such that
Xi and X j satisfy (ii). So. al ... ai-l are the labels of leaves at level 1 in T.
ai is the yield of the Xi-tree h etc.
As k ?: 2. at least one of the sons is an internal vertex. By the left-to-right
ordeling of leaves. a can be written as ala: ... am' where ai is obtained by
the concatenation of the labels of the leaves which are descendants of vertex
Vi' If Vi is an internal vertex, consider the subtree of T with Vi as its root. The
number of internal vertices of the subtree is less than k (as there are k internal
vertices in T and at least one of them, viz. its root, is not in the subtree). So
by induction hypothesis applied to the subtree, Xi ~ ai' If 1\ is not an internal
vertex. i.e. a leaf, then Xi = ai'
Using (6.1), we get
A ::::} XIX: ... XIII ~ a I X:X 3 ... XIII ... ~ aj a2 ••• cx,n = a,
i.e. A ~ ex. By the principle of induction. A ~ a whenever a is the yield
of an A-tree.
To prove the 'only if' part. let us assume that A ~ a. We have to
constmct an A-tree whose yield is a. We do this by induction on the number
of steps in A ~ a.
When A ::::} a, A -7 a is a production in P. If a = XIX: ... XIII' the
A-tree with yield a is constmcted and given as in Fig. 6.5. So there is basis
for induction. Assume the result for derivations in at most k steps. Let
A b (X: we can split this as A ::::} Xj ... XI/i k~ a. Now, A ::::} Xj XIII
implies A -7 XjX 2 .•. XIII is a production in P. In the derivation XjX:
XIII
k~ (X, either (i) Xi is not changed throughout the derivation, or (ii) Xi is
changed in some subsequent step. Let (Xi be the substring of a delived from Xi'
Then Xi ~ ai in (ii) and Xi = (Xi in (i). As G is context-free, in every step of
the delivation XIX: ... XIII ~ a, we replace a single variable by a string. As
aj, a: . ..., aI/I' account for all the symbols in a, we have a = ala2 ... a III'
A
Fig. 6.5 Derivation tree for one-step derivation.
We constmct the derivation tree with yield a as follows: As A -7 Xl' .. XIII
is in P. we constmct a tree with Tn leaves whose labels are Xj, ..., X IlI in the
left-to-light ordeling. This tree is given in Fig. 6.6. In (i) above, we leave the
vertex Vi as it is. In (ii). Xi ~ ai is less than k steps (as XI ... XI/I I/~ a). By
induction hypothesis there exists an Xi-tree T i with yield ai' We attach the tree
T i at the vertex Vi (i.e. Vi is the root of T;). The resulting tree is given in
Fig. 6.7. In this figure. let i and j be the first and the last indexes such that
Xi and X j satisfy (ii). So. al ... ai-l are the labels of leaves at level 1 in T.
ai is the yield of the Xi-tree h etc.