WEB LEXIKON: Ein Blick zurück
Hauptseite | Aktueller Wikipedia-Artikel

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 angenommen. stellt wie üblich die Menge der Nichtterminalsymbole, die Menge der Terminalsymbole, die Menge von Regeln und das Startsymbol dar (Einzelheiten siehe unter 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 , 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 ausgehend vom Startsymbol enthalten darf. 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).

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 , wobei ein Nichtterminal und ein Wort bestehend aus Terminalen und Nichtterminalen ist. Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen Kellerautomaten (NPDA) erkannt werden können. Eine Teilmenge dieser Sprachen bilden die theoretische Basis für die Syntax der meisten Programmiersprachen.

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 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 (), falls es eine Grammatik mit gibt. Man schreibt dann .

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.

Grammatik Regeln Sprachen Automaten
Typ-0 keine Einschränkungen rekursiv aufzählbar Turing-Maschine
Typ-1 kontextsensitiv linear platzbeschränkte nichtdeterministische Turing-Maschine
Typ-2 kontextfrei nichtdeterministischer Kellerautomat
Typ-3
regulär endlicher Automat

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




     
Das Web Lexikon "Ein Blick zurück" bietet die Moeglichkeit auf einfache Art und Weise in den "alten" Wikipedia-Beiträgen zu blättern. Das Lexikon spiegelt den Stand der freien Wikipedia-Enzyklopädie vom August 2004 wider. Sie finden hier in rund 120.000 Artikel aus dieser Zeit Informationen, Erklärungen, Definitionen, Empfehlungen, Beschreibungen, Auskünfte und Bilder. Ebenso kommen Begriffserklärung, Zusammenfassung, Theorie, Information, Beschreibung, Erklärung, Definition und Geschichte nicht zu kurz. Ein Lexikon das Auskunft, Bericht, Hinweis, Bedeutung, Bild, Aufklärung, Darstellung und Schilderung zu unterschiedlichsten Themen kompakt auf einer Seite bietet.
Impressum ^ nach oben ^