[Overview] [Previous] [Next]
Since the order in which we expand the variables
in a sentential form doesn't seem to make any difference
(the textbook contains a proof of this),
it would be nice to show a derivation in some way
that is independent of the order.
A derivation tree is a way of presenting
a derivation in an order-independent fashion.
For example, for the following derivation:
we would have the derivation tree:
This tree represents not just the given derivation, but
all the different orders in which the same productions
could be applied to produce the string abbc.
A partial derivation tree is any subtree of a
derivation tree such that, for any node of the subtree,
either all of its children are also in the subtree,
or none of them are.
The yield of the tree is the final string obtained by reading the leaves
of the tree from left to right, ignoring the s
(unless all the leaves are ,
in which case the yield is ).
The yield of the above tree is the string abbc, as expected.
The yield of a partial derivation tree that contains the
root is a sentential form.
Copyright © 1996 by David Matuszek
Last modified Feb 26, 1996