[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 directly derives ABC directly derives aABC directly derives aABcC directly derives aBcC directly derives abBcC directly derives abBc directly derives abbBc directly derives abbc

we would have the derivation tree:

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 empty strings (unless all the leaves are empty string, in which case the yield is empty string). 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