Chomsky Hierarchie

Überblick

• Einteilung in die Chomsky-Typen 0, 1, 2, 3:

  Typ	Grammatikart	Sprachtyp	akzeptierende Maschine
  0	unbeschränkt	aufzählbar	Turingmaschine
  1	kontextsensitiv	kontextsensitiv	linear beschränkte Turingmaschine
  2	kontextfrei	kontextfrei	Kellerautomat
  3	rechtslinear	regulär	endlicher Automat

• Folgende Abbildung zeigt den Umfang der verschiedenen Sprachtypen:
  

  Typ 3 ist also eine Teilmenge von Typ 2, welche eine Teilmenge von Typ 1 ist, welche wiederum eine Teilmenge von Typ 0 ist.

Durch die Einteilung in verschiedene Sprachtypen kann festgestellt werden, welcher Maschinentyp für die Erkennung von formalen Sprachen nötig ist. Im Folgenden werden Typ 2 und 3 genauer beschrieben.