182 &;\ Theory of Computer Science
Note: Vertices 4-6 are the sons of 3 written from the left, and 5 ~ aA5 is
in P. Vertices 7 and 8 are the sons of 5 written from the left, and A ~ ba
is a production in P. The vertex 5 is an internal vertex and its label is A, which
is a variable.
Ordering of Leaves from the Left
We can order all the vertices of a tree in the following way: The successors
of the root (i.e. sons of the root) are ordered from the left by the definition
(refer to Section 1.2). So the vertices at level 1 are ordered from the left. If
1'1 and 1'2 are any two vertices at levelland 1'1 is to the left of 1'2, then we
say that 1'1 is to the left of any son of 1'2' Also, any son of 1'1 is to the left
of 1'2 and to the left of any son of 1'2. Thus we get a left-to-right ordering of
vertices at level 2. Repeating the process up to level k, where k is the height
of the tree, we have an ordering of all vertices from the left.
Our main interest is in the ordering of leaves.
In Fig. 6.1, for example, the sons of the root are 2 and 3 ordered from the
left. So, the son of 2, namely 10, is to the left of any son of 3. The sons of
3 ordered from the left are 4-5-6. The vertices at level 2 in the left-to-right
ordering are 10-4-5-6. The vertex 4 is to the left of 6. The sons of 5 ordered
from the left are 7-8. So 4 is to the left of 7. Similarly, 8 is to the left of
9. Thus the order of the leaves from the left is 10-4-7-8-9.
Note: If we draw the sons of any vertex keeping in mind the left-to-right
ordering. we get the left-to-right ordering of leaves by 'reading' the leaves in
the anticlocbvise direction.
Definition 6.2 The yield of a derivation tree is the concatenation of the
labels of the leaves without repetition in the left-to-right ordering.
The yield of the derivation tree of Fig. 6.1. for example, is aabaa.
Note: Consider the derivation tree in Fig. 6.1. As the sons of I are 2-3 in
the left-to-right ordering, by condition (iv) of Definition 6.1, we have the
production 5 ~ 55. By applying the condition (iv) to other veltices, we get
the productions 5 ~ a. 5 ~ aA5, A ~ ba and 5 ~ a. Using these
productions. we get the following derivation:
5 ~ 55 ~ as ~ aaA5 ~ aaba5 ~ aabaa
Thus the yield of the de11vation tree is a sentential form in G.
Definition 6.3 A subtree of a derivation tree T is a tree (i) whose root is
some vertex v of T. (ii) whose vertices are the descendants of v together with
their labels, and (iii) whose edges are those connecting the descendants of v.
Figures 6.2 and 6.3. for example, give two subtrees of the derivation tree
shown in Fig. 6. L
Note: Vertices 4-6 are the sons of 3 written from the left, and 5 ~ aA5 is
in P. Vertices 7 and 8 are the sons of 5 written from the left, and A ~ ba
is a production in P. The vertex 5 is an internal vertex and its label is A, which
is a variable.
Ordering of Leaves from the Left
We can order all the vertices of a tree in the following way: The successors
of the root (i.e. sons of the root) are ordered from the left by the definition
(refer to Section 1.2). So the vertices at level 1 are ordered from the left. If
1'1 and 1'2 are any two vertices at levelland 1'1 is to the left of 1'2, then we
say that 1'1 is to the left of any son of 1'2' Also, any son of 1'1 is to the left
of 1'2 and to the left of any son of 1'2. Thus we get a left-to-right ordering of
vertices at level 2. Repeating the process up to level k, where k is the height
of the tree, we have an ordering of all vertices from the left.
Our main interest is in the ordering of leaves.
In Fig. 6.1, for example, the sons of the root are 2 and 3 ordered from the
left. So, the son of 2, namely 10, is to the left of any son of 3. The sons of
3 ordered from the left are 4-5-6. The vertices at level 2 in the left-to-right
ordering are 10-4-5-6. The vertex 4 is to the left of 6. The sons of 5 ordered
from the left are 7-8. So 4 is to the left of 7. Similarly, 8 is to the left of
9. Thus the order of the leaves from the left is 10-4-7-8-9.
Note: If we draw the sons of any vertex keeping in mind the left-to-right
ordering. we get the left-to-right ordering of leaves by 'reading' the leaves in
the anticlocbvise direction.
Definition 6.2 The yield of a derivation tree is the concatenation of the
labels of the leaves without repetition in the left-to-right ordering.
The yield of the derivation tree of Fig. 6.1. for example, is aabaa.
Note: Consider the derivation tree in Fig. 6.1. As the sons of I are 2-3 in
the left-to-right ordering, by condition (iv) of Definition 6.1, we have the
production 5 ~ 55. By applying the condition (iv) to other veltices, we get
the productions 5 ~ a. 5 ~ aA5, A ~ ba and 5 ~ a. Using these
productions. we get the following derivation:
5 ~ 55 ~ as ~ aaA5 ~ aaba5 ~ aabaa
Thus the yield of the de11vation tree is a sentential form in G.
Definition 6.3 A subtree of a derivation tree T is a tree (i) whose root is
some vertex v of T. (ii) whose vertices are the descendants of v together with
their labels, and (iii) whose edges are those connecting the descendants of v.
Figures 6.2 and 6.3. for example, give two subtrees of the derivation tree
shown in Fig. 6. L