The Wayback Machine - https://web.archive.org/web/20191113123733/https://www.seas.upenn.edu/~cit596/notes/dave/cfg7.html
[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