[Overview] [Previous] [Next]

Grammars

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*