hold and in which property 2 is replaced by
2a. Every leaf has a label from V ∪ T ∪ {λ},
is said to be a partial derivation tree.
The string of symbols obtained by reading the leaves of the tree from left to
right, omitting any λ’s encountered, is said to be the yield of the tree. The
descriptive term left to right can be given a precise meaning. The yield is the
string of terminals in the order they are encountered when the tree is traversed in
a depth-first manner, always taking the leftmost unexplored branch.
Example 5.6
Consider the grammar G, with productions
The tree in Figure 5.2 is a partial derivation tree for G, while the tree in Figure
5.3 is a derivation tree. The string abBbB, which is the yield of the first tree, is a
sentential form of G. The yield of the second tree, abbbb, is a sentence of L (G).
Figure 5.2
Figure 5.3
2a. Every leaf has a label from V ∪ T ∪ {λ},
is said to be a partial derivation tree.
The string of symbols obtained by reading the leaves of the tree from left to
right, omitting any λ’s encountered, is said to be the yield of the tree. The
descriptive term left to right can be given a precise meaning. The yield is the
string of terminals in the order they are encountered when the tree is traversed in
a depth-first manner, always taking the leftmost unexplored branch.
Example 5.6
Consider the grammar G, with productions
The tree in Figure 5.2 is a partial derivation tree for G, while the tree in Figure
5.3 is a derivation tree. The string abBbB, which is the yield of the first tree, is a
sentential form of G. The yield of the second tree, abbbb, is a sentence of L (G).
Figure 5.2
Figure 5.3