G = ({S, A, B, C}, {a, b, c}, S, P)

where

P = {SABC, AaA,
A,
BbB, B,
CcC, C}.

With this grammar, there is a choice of variables to expand. Here is a sample derivation:

If we always expanded the leftmost variable first,
we would have a *leftmost derivation:*

Conversely, if we always expanded the rightmost variable first,
we would have a *rightmost derivation:*

There are two things to notice here:

- Different derivations result in quite different sentential forms, but
- For a context-free grammar, it really doesn't make much difference in what order we expand the variables.

Copyright © 1996 by David Matuszek

Last modified Feb 26, 1996