The string "abab" can be generated from this grammar in
two distinct ways, as shown by the following derivation
trees:

Similarly, abab has two distinct leftmost derivations:

Likewise, abab has two distinct rightmost derivations:

Each derivation tree can be turned into a unique rightmost derivation, or into a unique leftmost derivation. Each leftmost or rightmost derivation can be turned into a unique derivation tree. So these representations are largely interchangeable.

Copyright © 1996 by David Matuszek

Last modified Mar 3, 1996