[Overview] [Previous] [Next]

Sentential Forms

A sentential form is the start symbol S of a grammar or any string in (V union T)* that can be derived from S.

Consider the linear grammar

({S, B}, {a, b}, S, {S goes to aS, Sgoes toB, Bgoes tobB, Bgoes toempty string}).

A derivation using this grammar might look like this:

S directly derives aS directly derives aB directly derives abB directly derives abbB directly derives abb

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