[Overview] [Previous] [Next]

Right-Linear Grammars

In general, productions have the form:

(V union T)plus goes to (V union T)star.

In a right-linear grammar, all productions have one of the two forms:

V goes to T*V
V goes to T*

That is, the left-hand side must consist of a single variable, and the right-hand side consists of any number of terminals (members of sigma) optionally followed by a single variable. (The "right" in "right-linear grammar" refers to the fact that, following the arrow, a variable can occur only as the rightmost symbol of the production.)

Copyright 1996 by David Matuszek
Last modified Feb 11, 1996