**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:- Right-linear (right-regular), with rules of the form or ; the structural descriptions generated with these grammars are right-branching.
- Left-linear (left-regular), with rules of the form or ; the structural descriptions generated with these grammars are left-branching.

Fri Nov 28 02:24:58 MET 1997