Theoretische Informatik

Grammatiken lassen sich, je nach dem, welchen Einschränkungen ihre Produktionen unterliegen, in vier Typen einteilen. Diese vier Grammatiktypen bilden die Chomsky-Hierarchie der Grammatiken, benannt nach dem Linguisten N. Chomsky.

Das Wortproblem

Gegeben sei ein Alphabet A, eine bestimmte Sprache L über A sowie ein Wort w ∈ A*. Das Wortproblem besteht darin, zu entscheiden, ob das Wort w ein Element der Sprache L ist oder nicht.

Um das Wortproblem für eine Sprache zu lösen, die durch eine Grammatik gegeben ist, muss geprüft werden, ob das gegebene Wort nach den Regeln der Grammatik aufgebaut ist oder nicht. In der Praxis stellt sich dieses Problem bei Programmiersprachen; hier wird geprüft, ob ein Programmtext den Syntaxregeln der Programmiersprache entspricht oder nicht. Ist dies nicht der Fall, etwa weil eine schließende Klammer fehlt, so kann das Programm nicht in eindeutiger Weise in Maschinenbefehle übersetzt werden.

Überraschenderweise stellt sich heraus, dass das Wortproblem im Allgemeinen nicht lösbar ist. Es ist im Allgemeinen nicht entscheidbar, ob eine gegebenes Wort w den Regeln einer gegebenen Grammatik G entspricht oder nicht.

Für einen speziellen Typ von Grammatiken, die monotonen Grammatiken, ist jedoch das Wortproblem stets lösbar, allerdings dauert die Überprüfung möglicherweise sehr lange. Für einen noch spezielleren Typ von Grammatiken, die kontextfreien Grammatiken, ist das Wortproblem dagegen sogar effizient lösbar, daher eignen sich diese am besten für Programmiersprachen. Schließlich gibt es einen wiederum noch spezielleren Typ von Grammatiken, die rechtslinearen Grammatiken, diese sind jedoch für Programmiersprachen nicht ausdrucksstark genug.

Diese vier Typen von Grammatiken werden auch als Typ-i-Grammatiken bezeichnet (i = 0, ..., 3); die zugehörigen Sprachen heißen Typ-i-Sprachen. Die vier entsprechenden Sprachklassen, bezeichnet mit ℒ_i, bilden die Chomsky-Hierarchie der Sprachklassen. Es gilt

ℒ₃  ⊂  ℒ₂  ⊂  ℒ₁  ⊂  ℒ₀

Später werden wir noch sehen, dass es auch eine entsprechende Chomsky-Hierarchie von Automaten gibt.

Typ-i-Grammatiken

Typ 0

Die Produktionen einer Typ-0-Grammatik unterliegen also keinerlei Einschränkungen. Auf der linken Seite einer Produktion steht ein beliebiges, nichtleeres Wort über dem Gesamtalphabet A = V ∪ T, auf der rechten Seite ebenfalls ein beliebiges, aber möglicherweise auch leeres Wort über A.

Typ 1

Eine Typ-1-Grammatik ist ein Spezialfall einer Typ-0-Grammatik.

Eine Produktion, deren linke Seite nicht länger ist als die rechte Seite, wird als monoton oder expandierend bezeichnet. In einer Typ-1-Grammatik sind alle Produktionen monoton, außer möglicherweise der Produktion Sε. Daher heißt eine Typ-1-Grammatik auch monotone Grammatik.

Wenn die Produktion Sε vorhanden ist, darf das Startsymbol S nicht auf der rechten Seite einer Produktion auf­treten. Denn sonst wäre es möglich, eine unzulässige, nicht monotone Produktion wie aBa durch die Kette der zulässigen Produktionen aBaS,  Sε nachzubilden.

Durch diese Bedingung ist die Eigenschaft der Monotonie auch auf Ableitungsfolgen übertragbar (außer auf die Ableitungsfolge Sε).

Durch ein einfaches Umformungsverfahren lässt sich ein rekursives Startsymbol aus einer Grammatik zu entfernen.

Typ 2

Bei den Produktionen einer Typ-2-Grammatik steht auf der linken Seite stets nur eine einzige Variable. Auf der rechten Seite steht ein beliebiges, möglicherweise auch leeres Wort über dem Gesamtalphabet A.

Eine Typ-2-Grammatik heißt auch kontextfreie Grammatik.

Es ist möglich, eine Typ-2-Grammatik in eine äquivalente Typ-2-Grammatik umzuformen, die den Bedingungen des Typs 1 entspricht. Wir verlangen nicht, dass eine Typ-2-Grammatik von vorneherein diesen Bedingungen entspricht. Nach den entsprechenden Umformungen jedoch ist eine Typ-2-Grammatik ein Spezialfall einer Typ-1-Grammatik. Diese Umformungen bezeichnen wir als Basis-Normalisierung. Im Wesentlichen geht es darum, Epsilon-Produktionen, die ja nicht der Monotonie-Bedingung des Typs 1 entsprechen, zu entfernen.

Typ 3

Definition:  Eine Grammatik G = (V, T, P, S) heißt Typ-3-Grammatik, wenn alle Produktionen die Form

X		aY	oder
X		a	oder
X		ε

mit X, Y ∈ V und a ∈ T haben.

Eine Typ-3-Grammatik ist somit ein Spezialfall einer Typ-2-Grammatik und, nach einer Basis-Normalisierung, auch ein Spezialfall einer Typ-1-Grammatik.

Eine Typ-3-Grammatik heißt auch rechtslineare Grammatik.

Typ-i-Sprachen

Da die Typ-i-Grammatiken jeweils Spezialfälle der Typ-i-1-Grammatiken sind (i = 1, 2, 3), gilt für die von diesen Grammatiktypen erzeugten Sprachklassen zunächst

ℒ_i  ⊆  ℒ_i-1

Wir werden im Folgenden sehen, dass die Sprachklassen tatsächlich sogar echt ineinander enthalten sind.

Die vier Sprachklassen ℒ₀, ..., ℒ₃ bilden die Chomsky-Hierarchie der Typ-i-Sprachen. Die Chomsky-Hierarchie lässt sich, wie hier geschehen, durch eine entsprechende Hierarchie von Grammatiktypen charakterisieren, aber auch durch eine entsprechende Hierarchie von Automatentypen sowie eine Hierarchie von String-Turingmaschinen.