Die Chomsky-Hierachie

Die Chomsky-Hierachie umfasst vier Typen von Grammatiken:

  • Typ-o-Grammatik
  • Typ-1-Grammatik
  • Typ-2-Grammatik
  • Typ-3-Grammatik

Typ-0-Grammatik

Die Menge der durch die Typ-0-Grammatik erzeugbaren Wörter stellt die größte Menge an erzeugbaren Wörtern dar. Die Typ-0-Grammatik ist nicht eingeschränkt und umfasst somit alle anderen Grammatiken. Eine Grammatik vom Typ 0 ist ganz einfach eine formale Grammatik.

Typ-1-Grammatik

Die Menge der durch die Typ-1-Grammatik der Chomsky-Hierachie erzeugbaren Wörter stellt eine Teilmenge der Menge der von der Typ-0-Grammatik erzeugbaren Wörter dar. Eine Typ-1-Grammatik der Chomsky-Hierachie ist kontextsensitiv.

Typ-2-Grammatik

Eine Typ-2-Grammatik der Chomsky-Hierachie ist kontextfrei und die Menge der durch die Typ-2-Grammatik erzeugbaren Wörter stellt eine Teilmenge der Wörter dar, die durch die Typ-0- und Typ-1-Grammatik erzeugt werden können.

Typ-3-Grammatik

Eine Typ-3-Grammatik kann durch einen regulären Ausdruck dargestellt werden, erzeugt eine reguläre Sprache und stellt die am stärksten eingeschränkte Grammatik der Chomsky-Hierachie dar. Typ-3-Grammatiken sind die regulären Grammatiken.

Zusammenfassend gilt also: 

Typ-3-Sprachen sind Teilmenge der Typ-2-Sprachen sind Teilmenge der Typ-1-Sprachen sind Teilmenge der Typ-0-Sprachen

Diese Aufteilung bzgl. der Mächtigkeit der Mengen orientiert sich also an der generativen Kapazität der Grammatiken.