Direkt zum Inhalt

Lexikon der Mathematik: Chomsky-Grammatik

meist im Zusammenhang mit der Einordnung der Sprache bzw. Grammatik in die Chomsky–Hierarchie verwendeter Begriff (Grammatik).

Die Chomsky–Hierarchie ordnet jeder Grammatik einen Typ zu. Jede Grammatik ist vom Typ 0. Jede kontextsensitive Grammatik ist vom Typ 1, jede kontextfreie Grammatik vom Typ 2. Jede linkslineare und jede rechtslineare Grammatik schließlich ist vom Typ 3.

Eine Sprache L ist vom Typ i, falls es eine Grammatik vom Typ i gibt, die L erzeugt. Jede Sprache vom Typ i ist wegen der zunehmenden Restriktionen für die Einordnung automatisch auch vom Typ 0,…, i − 1. Daher wird oft nur das maximale i als Typ der Sprache bezeichnet.

Zu jedem Typ gibt es Sprachen, die von diesem, aber nicht dem nächsthöheren Typ sind, z. B. ist {anbn | n ≥ 1} vom Typ 2, aber nicht vom Typ 3, und {anbncn | n ≥ 1} vom Typ 1, aber nicht vom Typ 2.

Für verschiedene Sprachtypen gibt es Standardverfahren zur Syntaxanalyse (Kellerautomat für Typ–2–Sprachen, Automat für Typ–3–Sprachen). Die Zugehörigkeit zu einem Typ beweist man durch Angabe einer Grammatik des Typs, die Nichtzugehörigkeit oft durch Anwendung eines sog. Pumping-Lemmas.

Die Einordnung in die Chomsky–Hierarchie ist ein gutes Maß für die Kompliziertheit einer Sprache. Die meisten gängigen Programmiersprachen lassen sich im wesentlichen auf der Basis von Typ–2–Grammatiken beschreiben, einfache Teilstrukturen wie Bezeichner, Zahlen, aber auch Suchmuster vieler Textverarbeitungssysteme werden oft durch Typ-3-Sprachen beschrieben.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.