[Overview] [Previous] [Next]

Grammars

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

A production of an unrestricted grammar has the form

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

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

xVy goes to x(V union T)stary or A goes to B, |A| <= |B|, A contains a variable

Productions of a context-free grammar have the form

V goes to (V union T)star

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

V goes to T*V V goes to T*

whereas a left-linear grammar has productions of the forms

V goes to VT* V goes to T*


Copyright 1996 by David Matuszek
Last modified Apr 23, 1996