Consider the linear grammar

({S, B}, {a, b}, S, {S aS, SB, BbB, B}).

A derivation using this grammar might look like this:

Each of {S, aS, aB, abB, abbB, abb} is a sentential form.

Because this grammar is linear, each sentential form has at most one variable. Hence there is never any choice about which variable to expand next.

Copyright © 1996 by David Matuszek

Last modified Feb 26, 1996