[Overview] [Previous] [Next]

# Derivation Trees

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:

S ABC aABC aABcC aBcC abBcC abBc abbBc abbc

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.