A *grammar* G is a quadruple G = (V, T, S, P)

where

- V is a finite set of (meta)symbols, or
*variables*. - T is a finite set of
*terminal symbols*. - S V is
a distinguished element of V called the
*start symbol*. - P is a finite set of
*productions*(or*rules*).

A production of an **unrestricted grammar** has the form

(V T) (V T)

Productions of a **context-sensitive grammar** can be defined in either of
two ways:

xVy x(V T)y or A B, |A| |B|, A contains a variable

Productions of a **context-free grammar** have the form

V (V T)

A **regular grammar** is either a right-linear grammar or a left-linear
grammar. A right-linear grammar has productions of the forms

V T*V V T*

whereas a left-linear grammar has productions of the forms

V VT* V T*

Copyright © 1996 by David Matuszek

Last modified Apr 23, 1996