next up previous contents
Next: Some useful properties of Up: Formalisms Previous: Formal Grammars

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 tex2html_wrap_inline1436 where tex2html_wrap_inline1456 and tex2html_wrap_inline1458 are arbitrary strings over a vocabulary V and tex2html_wrap_inline1462.

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 tex2html_wrap_inline1464 tex2html_wrap_inline1466 tex2html_wrap_inline1456 B tex2html_wrap_inline1458 where tex2html_wrap_inline1474, tex2html_wrap_inline1476, tex2html_wrap_inline1478, or of the form tex2html_wrap_inline1480, where tex2html_wrap_inline1482 is the initial symbol and tex2html_wrap_inline1484 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 tex2html_wrap_inline1486, where tex2html_wrap_inline1488, tex2html_wrap_inline1490. 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 tex2html_wrap_inline1492 or tex2html_wrap_inline1494; the structural descriptions generated with these grammars are right-branching.
  2. Left-linear (left-regular), with rules of the form tex2html_wrap_inline1496 or tex2html_wrap_inline1494; the structural descriptions generated with these grammars are left-branching.


Dafydd Gibbon
Fri Nov 28 02:24:58 MET 1997