Chomsky-Hierarchie

Die Chomsky-Hierarchie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen. Sie wurde 1956 von Noam Chomsky beschrieben. Die vier von Chomsky beschriebenen Grammatik-Typen entstehen dabei ausgehend von einer Grund-Grammatik (der Typ-0-Grammatik) dergestalt, dass zunehmend Einschränkungen bezüglich der für den Typ erlaubten Produktionsregeln gemacht werden. Die Typ-1-Grammatik ist also ein Spezialfall der Typ-0-Grammatik, die Typ-2-Grammatik ein Spezialfall der Typ-1-Grammatik usw.

Sei im Folgenden die formale Grammatik

Die Hierarchie

Die Chomsky-Hierarchie besteht aus folgenden Ebenen:

Typ-0-Grammatiken

Typ-0-Grammatiken werden auch unbeschränkte Grammatiken genannt. Es handelt sich dabei um alle definierbaren Grammatiken.

Man schreibt

Jede Typ-0-Grammatik erzeugt eine Sprache, die von einer Turing-Maschine akzeptiert werden kann und für jede Sprache die von einer Turing-Maschine akzeptiert werden kann existiert eine Typ-0-Grammatik, die diese Sprache erzeugt. Diese Sprachen sind auch bekannt als die rekursiv aufzählbaren Sprachen (oft auch semientscheidbare Sprachen genannt). Man beachte, dass sich diese Menge von Sprachen von der Menge der rekursiven Sprachen (oft auch entscheidbare Sprachen genannt) unterscheidet, welche durch Turing-Maschinen erkannt werden können, d.h. die zugehörige Turingmaschine hält bei jedem Wort und liefert als Ergebnis 0 (Wort gehört nicht zur Sprache) oder 1 (Wort gehört zur Sprache).

Typ-1-Grammatiken

Typ-1-Grammatiken werden auch kontextsensitive Grammatiken genannt. Es handelt sich dabei um Grammatiken mit

Man schreibt

Sie erzeugen genau die kontextsensitiven Sprachen, d.h. jede Typ-1-Grammatik erzeugt eine kontextsenstive Sprache und zu jeder kontextsensitiven Sprache existiert eine Typ-1-Grammatik, die diese erzeugt.

Typ-1-Grammatiken besitzen nur Regeln der Form

Die einzige Ausnahme ist, dass die Grammatik die Regel

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

Typ-2-Grammatiken

Typ-2-Grammatiken werden auch kontextfreie Grammatiken genannt. Es handelt sich dabei um Grammatiken mit

Man schreibt

Sie erzeugen genau die kontextfreien Sprachen, d.h. jede Typ-2-Grammatik erzeugt eine kontextfreie Sprache und zu jeder kontextfreien Sprache existiert eine Typ-2-Grammatik, die diese erzeugt.

Typ-2-Grammatiken besitzen nur Regeln der Form

Siehe auch: Backus-Naur-Form

Typ-3-Grammatiken

Typ-3-Grammatiken werden auch reguläre Grammatiken genannt. Es handelt sich dabei um Grammatiken mit

und

Man schreibt

Sie erzeugen genau die regulären Sprachen, d.h. jede Typ-3-Grammatik erzeugt eine reguläre Sprache und zu jeder regulären Sprache existiert eine Typ-3-Grammatik, die diese erzeugt.

Typ-3-Grammatiken besitzen entweder nur Regeln, die auf der linken Seite aus einem Nichtterminal und auf der rechten Seite aus einem Terminal, eventuell gefolgt von einem Nichtterminal bestehen (rechtsreguläre Grammatik) oder nur Regeln, die auf der linken Seite aus einem Nichtterminal und auf der rechten Seite aus einem Terminal, eventuell mit vorangestelltem Nichtterminal bestehen (linksreguläre Grammatik).

Zu jeder linksregulären Grammatik gibt es auch eine rechtsreguläre Grammatik (und umgekehrt), die die selbe Sprache erzeugt. Aus demselben Grund wie bei Typ-1-Grammatiken ist auch hier die Regel

als Ausnahme erlaubt, allerdings nur, wenn S nicht auf der rechten Seite einer Regel erscheint.

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.

Chomsky-Hierarchie für formale Sprachen

Eine formale Sprache

ist vom Typ i (

), falls es eine Grammatik

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:

wobei gelegentlich auch folgende Symbole verwendet werden:

Übersicht

Die folgende Tabelle fasst die vier Grammatiktypen, die Form ihrer Regeln, die Sprachen die sie erzeugen und die Automatentypen die sie erkennen zusammen.

Menschliche Sprachen

Von den formalen Sprachen werden die menschlichen Sprachen unterschieden. Um jedoch maschinelle Übersetzung, Expertensysteme und ähnliches zu ermöglichen, muss menschliche Sprache als formale Sprache dargestellt werden.

Ließe sich für eine menschliche Sprache eine Grammatik vom Typ 2 oder 3 aufstellen, so könnte diese auf einem Computer effizient ausgeführt werden. Wäre menschliche Sprache vom Typ 0, so wäre sie unlösbar (da es keine Computer gibt, die diese Aufgabe in endlicher Zeit bearbeiten können). Eine Hypothese besagt, dass die menschliche Sprache schwach kontext-sensitiv ist (d.h. der Großteil menschlicher Sprache lässt sich kontextfrei darstellen, einige Aspekte jedoch benötigen eine kontextsensitive Repräsentation, ohne dass die Mächtigkeit von Typ-1-Grammatiken dabei ausgeschöpft wird).

Literatur

• Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pages 113-124
• Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pages 91-112