Next: Some useful properties of
Previous: 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:
- 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