example, Figure 5.1 shows part of a derivation tree representing the production
In a derivation tree, a node labeled with a variable occurring on the left side of a
production has children consisting of the symbols on the right side of that
production. Beginning with the root, labeled with the start symbol and ending in
leaves that are terminals, a derivation tree shows how each variable is replaced
in the derivation. The following definition makes this notion precise.
Figure 5.1
Definition 5.3
Let G = (V, T, S, P) be a context-free grammar. An ordered tree is a derivation
tree for G if and only if it has the following properties.
1. The root is labeled S.
2. Every leaf has a label from T ∪ {λ}.
3. Every interior vertex (a vertex that is not a leaf) has a label from V.
4. If a vertex has label A ∈ V, and its children are labeled (from left to right)
a 1 , a 2 ,…, a n , then P must contain a production of the form
5. A leaf labeled λ has no siblings, that is, a vertex with a child labeled λ can
have no other children.
A tree that has properties 3, 4, and 5, but in which 1 does not necessarily