[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