Theoretische Informatik

Chomsky-Hierarchie der Grammatiktypen

 aufwärts

Grammatiken lassen sich, je nach dem, welchen Ein­schränkungen ihre Produktionen unterliegen, in vier Typen einteilen. Diese vier Grammatik­typen bilden die Chomsky-Hierarchie der Grammatiken, benannt nach dem Linguisten N. Chomskyzur Person.

Das Wortproblem

Gegeben sei ein Alphabet A, eine bestimmte Sprache L über A sowie ein Wort w Element 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 Programmier­sprachen; hier wird geprüft, ob ein Programmtext den Syntaxregeln der Programmier­sprache entspricht oder nicht. Ist dies nicht der Fall, etwa weil eine schließende Klammer fehlt, so kann das Programm nicht in eindeutiger Weise in Maschinen­befehle übersetzt werden.

Überraschender­weise 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öglicher­weise sehr lange. Für einen noch spezielleren Typ von Grammatiken, die kontext­freien Grammatiken, ist das Wortproblem dagegen sogar effizient lösbar, daher eignen sich diese am besten für Programmier­sprachen. Schließlich gibt es einen wiederum noch spezielleren Typ von Grammatiken, die rechts­linearen Grammatiken, diese sind jedoch für Programmier­sprachen nicht ausdrucks­stark 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 Sprach­klassen, bezeichnet mit i, bilden die Chomsky-Hierarchie der Sprach­klassen. Es gilt

3  echt enthalten in  2  echt enthalten in  1  echt enthalten in  0

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

Typ-i-Grammatiken

Typ 0

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

ugeht über nachv

mit u Element A+, v Element A* haben.

Die Produktionen einer Typ-0-Grammatik unterliegen also keinerlei Ein­schränkungen. Auf der linken Seite einer Produktion steht ein beliebiges, nichtleeres Wort über dem Gesamt­alphabet A = V vereinigt T, auf der rechten Seite ebenfalls ein beliebiges, aber möglicher­weise auch leeres Wort über A.

Typ 1

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

ugeht über nachv   mit   |u|kleiner gleich|v|

haben, d.h. wenn die linke Seite einer Produktion ist nie länger als die rechte Seite. Als einzige Ausnahme ist die Produktion

Sgeht über nachε

zugelassen, um das leere Wort ε zu erzeugen. Dann aber darf das Startsymbol S nicht rekursiv sein, d.h. nicht auf der rechten Seite einer Produktion auftreten.

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öglicher­weise der Produktion Sgeht über nachε. Daher heißt eine Typ-1-Grammatik auch monotone Grammatik.

Wegener, S. 128

Wenn die Produktion Sgeht über nachε vorhanden ist, darf das Startsymbol S nicht auf der rechten Seite einer Produktion auftreten. Denn sonst wäre es möglich, eine unzulässige, nicht monotone Produktion wie aBgeht über nacha durch die Kette der zulässigen Produktionen aBgeht über nachaS,  Sgeht über nachε nachzubilden.

Durch diese Bedingung ist die Eigenschaft der Monotonie auch auf Ableitungs­folgen übertragbar (außer auf die Ableitungs­folge Sgeht über nachε).

Durch ein einfaches Umformungs­verfahren lässt sich ein rekursives Startsymbol aus einer Grammatik zu entfernen.

Typ 2

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

Xgeht über nachv

mit X Element V, v Element A* haben.

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öglicher­weise auch leeres Wort über dem Gesamt­alphabet 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

Xgeht über nachaY    oder
Xgeht über nacha    oder
Xgeht über nachε

mit X, Y Element V und a Element 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 rechts­lineare 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 Grammatik­typen erzeugten Sprach­klassen zunächst

i  enthalten in  i-1

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

Die vier Sprach­klassen 0, ..., 3 bilden die Chomsky-Hierarchie der Typ-i-Sprachen. Die Chomsky-Hierarchie lässt sich, wie hier geschehen, durch eine entsprechende Hierarchie von Grammatik­typen charakterisieren, aber auch durch eine entsprechende Hierarchie von Automaten­typen sowie eine Hierarchie von String-Turing­maschinen.

 

Weiter mit:  [Typ-3-Grammatiken für reguläre Sprachen]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 27.08.2010   Updated: 13.05.2016
Valid HTML 4.01 Transitional