The Chomsky Hierarchy of formal grammars

Type 0:

Unrestricted rewriting systems. The languages defined by Type 0 grammars are accepted by Turing machines; Chomskyan transformations are defined as Type 0 grammars. Type 0 grammars have rules of the form where and are arbitrary strings over a vocabulary V and .

Type 1:

Context-sensitive grammars. The languages defined by Type 1 grammars are accepted by linear bounded automata; the syntax of some natural languages (including Dutch, Swiss German and Bambara), but not all, is generally held in computational linguistics to have structures of this type. Type 1 grammars have rules of the form B where , , , or of the form , where is the initial symbol and is the empty string.

Type 2:

Context-free grammars. The languages defined by Type 2 grammars are accepted by push-down automata; the syntax of natural languages is definable almost entirely in terms of context-free languages and the tree structures generated by them. Type 2 grammars have rules of the form , where , . There are special `normal forms', e.g. Chomsky Normal Form or Greibach Normal Form, into which any CFG can be equivalently converted; they represent optimisations for particular types of processing.

Type 3:

Regular grammars. The languages defined by Type 3 grammars are accepted by finite state automata; morphological structure and perhaps all the syntax of informal spoken dialogue is describable by regular grammars. There are two kinds of regular grammar:

1. Right-linear (right-regular), with rules of the form or ; the structural descriptions generated with these grammars are right-branching.
2. Left-linear (left-regular), with rules of the form or ; the structural descriptions generated with these grammars are left-branching.