in n steps, and
Since by the inductive assumption there is a partial derivation tree with yield
xAy, and since the grammar must have production A → a 1 a 2 …a m , we see that by
expanding the leaf labeled A, we get a partial derivation tree with yield
xa 1 a 2 …a m y = w. By induction, we therefore claim that the result is true for all
sentential forms.
In a similar vein, we can show that every partial derivation tree represents
some sentential form. We will leave this as an exercise.
Since a derivation tree is also a partial derivation tree whose leaves are
terminals, it follows that every sentence in L (G) is the yield of some derivation
tree of G and that the yield of every derivation tree is in L(G).
Derivation trees show which productions are used in obtaining a sentence,
but do not give the order of their application. Derivation trees are able to
represent any derivation, reflecting the fact that this order is irrelevant, an
observation that allows us to close a gap in the preceding discussion. By
definition, any w ∈ L(G) has a derivation, but we have not claimed that it also
had a leftmost or rightmost derivation. However, once we have a derivation tree,
we can always get a leftmost derivation by thinking of the tree as having been
built in such a way that the leftmost variable in the tree was always expanded
first. Filling in a few details, we are led to the not surprising result that any w ∈
L(G) has a leftmost and a rightmost derivation (for details, see Exercise 25 at the
end of this section).
EXERCISES
1. Complete the arguments in Example 5.2, showing that the language given is
generated by the grammar.
2. Draw the derivation tree corresponding to the derivation in Example 5.1.
Since by the inductive assumption there is a partial derivation tree with yield
xAy, and since the grammar must have production A → a 1 a 2 …a m , we see that by
expanding the leaf labeled A, we get a partial derivation tree with yield
xa 1 a 2 …a m y = w. By induction, we therefore claim that the result is true for all
sentential forms.
In a similar vein, we can show that every partial derivation tree represents
some sentential form. We will leave this as an exercise.
Since a derivation tree is also a partial derivation tree whose leaves are
terminals, it follows that every sentence in L (G) is the yield of some derivation
tree of G and that the yield of every derivation tree is in L(G).
Derivation trees show which productions are used in obtaining a sentence,
but do not give the order of their application. Derivation trees are able to
represent any derivation, reflecting the fact that this order is irrelevant, an
observation that allows us to close a gap in the preceding discussion. By
definition, any w ∈ L(G) has a derivation, but we have not claimed that it also
had a leftmost or rightmost derivation. However, once we have a derivation tree,
we can always get a leftmost derivation by thinking of the tree as having been
built in such a way that the leftmost variable in the tree was always expanded
first. Filling in a few details, we are led to the not surprising result that any w ∈
L(G) has a leftmost and a rightmost derivation (for details, see Exercise 25 at the
end of this section).
EXERCISES
1. Complete the arguments in Example 5.2, showing that the language given is
generated by the grammar.
2. Draw the derivation tree corresponding to the derivation in Example 5.1.