Kleines Nachschlagewerk Informatik
Chomsky-Hierarchie
Worum geht es?
Bisher konnte man erkennen, dass formale Sprachen in eine Hierarchie gebracht werden können. Je lockerer die Regeln sind, desto mehr Möglichkeiten hat man bei der Gestaltung der Grammatik.

Zu jeder Grammatik gehört ein Automat, der Wörter dieser Sprache erkennen kann. Je komplexer die Sprache, desto komplexer ist auch der Automat.

Es ist nun an der Zeit, Sprachen und Automaten zusammenfassend in eine Hierarchie zu bringen.
Die Chomsky-Hierarchie
Nach Noam Chomsky ergibt sich folgende Sprachhierarchie, die um die Automaten ergänzt wurde.

SpracheGrammatikerkennender Automat
Typ 3reguläre Spracheendlicher Automat
Typ 2kontextfreie SpracheKellerautomat
Typ 1kontextsensitive Sprachelinear beschränkter Automat
Typ 0rekursiv aufzählbare SpracheTuringmaschine