Chomsky-Hierarchie
Die Chomsky-Hierarchie ist eine Hierarchie von Klassen formaler Grammatiken die formale Sprachen erzeugen. Sie wurde 1956 von Noam Chomsky beschrieben.Eine formale Grammatik besteht aus Terminal-Symbolen, Nichtterminal-Symbolen (darunter das Startsymbol) und Produktions-Regeln. Die Grammatik definiert dann eine formale Sprache, die aus allen Wörtern besteht, die nur aus Terminal-Symbolen bestehen und vom Startsymbol abgeleitet werden können.
Die Hierarchie
Die Chomsky-Hierarchie besteht aus folgenden Ebenen:
Reguläre Sprachen können alternativ auch durch reguläre Ausdrücke beschrieben werden und die regulären Sprachen sind genau die Sprachen, die von endlichen Automaten erkannt werden können.
Sie werden gewöhnlich genutzt, um Suchmuster oder die lexikalische Struktur von Programmiersprachen zu definieren.
, wobei 
ein Nichtterminal und 
Wörter bestehend aus Terminalen und Nichtterminalen sind. Die Wörter 
und 
können leer sein, aber 
muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten. Die einzige Ausnahme ist, dass die Grammatik die Regel 
enthalten darf, wobei 
das Startsymbol und 
(wie oben erläutert) das leere Wort ist. Diese Regel wird eventuell benötigt, um das leere Wort ableiten zu können. Die kontextsensitiven Sprachen sind genau die Sprachen, die von einem nichtdeterministischen LBA erkannt werden können, d.h. von einer nichtdeterministischen Turing-Maschine, deren Band linear durch die Länge der Eingabe beschränkt ist (d.h. es gibt eine konstante Zahl 
so dass das Band der Turing-Maschine höchstens 
Felder besitzt, wobei 
die Länge des Eingabewortes ist).
, wobei ein Nichtterminal und ein Wort bestehend aus Terminalen und Nichtterminalen ist. Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen Kellerautomaten erkannt werden können. Eine Teilmenge dieser Sprachen bilden die theoretische Basis für die Syntax der meisten Programmiersprachen. als Ausnahme erlaubt, allerdings nur, wenn nicht auf der rechten Seite einer Regel erscheint.
Jede reguläre Sprache ist kontextfrei, jede kontextfreie Sprache ist kontextsensitiv und jede kontextsensitive Sprache ist rekursiv aufzählbar.
Dabei handelt es sich um echte Teilmengenbeziehungen, d.h. es gibt rekursive aufzählbare Sprachen, die nicht kontextsensitiv sind, kontextsensitive Sprachen, die nicht kontextfrei sind und kontextfreie Sprachen, die nicht regulär sind.
Formal ausgedrückt bedeutet dies für die Klassen der durch die obigen Grammatiken erzeugten Sprachen:
Die folgende Tabelle fasst die vier Grammatiktypen, die Form ihrer Regeln, die Sprachen die sie erzeugen und die Automatentypen die sie erkennen zusammen.
| kontextsensitiv
| linear platzbeschränkte nichtdeterministische Turing-Machine
|-----
| Typ-2 ||
| kontextfrei
| nichtdeterministischer Kellerautomat
|-----
| Typ-3
| 
| regulär || endlicher Automat
|}
