Chomsky-Grammatik

Chomsky-Grammatik ist eine Bezeichnung für formal definierbare Grammatikmodelle, welche Sprachen beliebigen Typs erzeugen und somit auch beschreiben können.

Kommentare

Eine Chomsky-Grammatik wird als Viertupel G = (N, T, P, S) definiert (N-Tupel), für das gilt:

(a) N ist eine endliche, nichtleere Menge von Zeichen, sog. Nicht-Terminalsymbolen;

(b) T ist eine endliche, nichtleere Menge von Zeichen, sog. End- oder Terminalsymbolen;

(c) N und T sind disjunkt;

(d) S ist ein Element von N und heißt Anfangs- oder Startsymbol oder Axiom;

(e) P ist eine endliche Menge von Ersetzungsregeln.

Chomsky-Grammatiken werden entsprechend ihrer Generativen Kapazität (auch Generative Mächtigkeit, vgl. Miller (2000)) in der Chomsky-Hierarchie klassifiziert; diese spiegelt die Leistungsfähigkeit einer Grammatik im Hinblick darauf wider,

(a) welche Sprachtypen eine Chomsky-Grammatik erzeugen kann und

(b) mit welcher Art und mit welchem Grad an Adäquatheit sie eine gegebene Sprache erfassen kann: Ausgehend von einer Grund-Grammatik, der sog. Typ-0-Grammatik, werden hierbei zunehmend Einschränkungen bezüglich der für den jeweiligen Typ erlaubten Produktionsregeln gemacht.

Grammatiken sind vom Typ 0, wenn sie dem Aufbau einer Grammatik entsprechen, sie werden auch als unbeschränkt bezeichnet.

Typ-1-Grammatiken heißen kontextsensitiv und haben auf der linken Seite einer Regel immer einen gleichlangen oder längeren Ausdruck als auf der rechten Seite. Die Abbildung auf das leere Wort ist zulässig, sofern das Terminal auf keiner rechten Seite vorkommt.

Typ-2-Grammatiken heißen kontextfrei und haben zusätzlich auf der rechten Seite nur Terminale.

Typ-3-Grammatiken heißen regulär oder rechtslinear und haben zusätzlich auf der linken Seite einer Regel maximal ein Terminal.

Typ-1-Grammatiken sind ein Spezialfall der Typ-0-Grammatiken, Typ-2-Grammatiken ein Spezialfall der Typ-1-Grammatiken usw., d. h. eine reguläre Sprache ist kontextfrei, eine kontextfreie Sprache ist kontextsensitiv und eine kontextsensitive Sprache ist unbeschränkt (auch: rekursiv aufzählbar).

Jeder Grammatik-Typ kann durch einen entsprechenden Automat beschrieben werden: Turingmaschinen entsprechen dem Typ 0, linear beschränkte Automaten dem Typ 1, Kellerautomaten stehen für Typ 2 und endliche Automaten für Typ 3.

Da eine Chomsky-Grammatik keine Regeln aufweist, die sich auf den Gebrauch sprachlicher Zeichen beziehen, setzt sie, falls sie zur Beschreibung natürlicher Sprachen verwendet wird, eine Idealisierung des Gebrauchs sprachlicher Strukturen voraus, die sich in den Begriffen Kompetenz vs. Performanz, Native Speaker und Idealer Sprecher-Hörer widerspiegelt.

Siehe auch

Chomsky-Normalform

Link

Chomsky-Grammatik in Norbert Fries, Online Lexikon Linguistik

Literatur

• Berwick, R. C. Strong Generative Capacity, Weak Generative Capacity, and Modern Linguistic Theories. Computational Linguistics 1984/10, 189–202.
• Chomsky, N. The Logical Structure of Linguistic Theory. Cambridge, Mass. 1955; N. Y. 1975.
• – Ders., Three Models for the Description of Language. IRE Transactions on Information Theory 1956/2, 113–124.
• – Ders., On Certain Formal Properties of Grammars. Information and Control 1959/1, 91–112.
• Hopcroft, J. E. et al., Introduction to Automata Theory, Languages, and Computation. Boston 2001 [Dt.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Bonn 2002].
• Klenk,U. Formale Sprachen mit Anwendungen auf die Beschreibung natürlicher Sprachen. Tübingen 1980.
• – Dies., Formale Sprachen. HSK 9, 1576-1605.
• Miller,P. Strong Generative Capacity: The Semantics of Linguistic Formalism. Chicago 2000.
• Stucky,P. et al., Automaten, Sprachen, Berechenbarkeit. Stuttgart 1992.