Chomsky-Hierarchie

Der amerikanische Sprachwissenschaftler A. Noam Chomsky (*07.12.1928) untersuchte u.a. [interner Verweis =>]Grammatiken und ihre Unterschiede bezüglich der Sprachen, die sie erzeugen können. (Man spricht hierbei von der generativen Mächtigkeit / der Leistungsfähigkeit einer Grammatik - Eingeschränkte Grammatiken können auch nur eingeschräkte Sprachen erzeugen.)
Seine Ergebnisse aus diesen Betrachtungen veröffentlichte er 1959 mit der nach ihm benannten Hierarchie für Sprachen und [interner Verweis =>]Grammatiken:

[interner Verweis =>]Grammatik der Stufe 0:
Diese [interner Verweis =>]Grammatik ohne jegliche Einschränkung erzeugt eine Menge von Sprachen, die hier mit CH bezeichnet wird.
[interner Verweis =>]Grammatik der Stufe 1:
Diese [interner Verweis =>]Grammatik ist kontextsensitiv und erzeugt eine Menge von Sprachen, die hier mit CS bezeichnet wird.
[interner Verweis =>]Grammatik der Stufe 2:
Diese [interner Verweis =>]Grammatik ist kontextfrei und erzeugt eine Menge von Sprachen, die hier mit CF bezeichnet wird.
[interner Verweis =>]Grammatik der Stufe 3:
Diese [interner Verweis =>]Grammatik ist links- oder rechtslinear und erzeugt eine Menge von Sprachen, die hier mit LL bzw. RL bezeichnet wird. (RL = LL)
Für die so erzeugten Sprachen gilt nun folgende echte Teilmengenbeziehung:
(LL=RR) Ì (CF) Ì (CS) Ì (CH)

OperationTyp 0Typ 1Typ 2Typ 3
Vereinigungjajajaja
Schnittjajaneinja
Komplementneinjajanein
Verkettungjajajaja
*-Bildungjajajaja
Abschlusseigenschaften: Da formale Sprachen Mengen von Zeichenketten sind, lassen sich folgende mengen- und zeichenspezifische Operationen anwenden: Vereinigung, Schnitt, Differenz, Komplement, Verkettung, *-Bildung. Dabei gelten folgende Eigenschaften:

Desweiteren kann man die verschiedenen Automatenmodelle und ihre jeweils akzeptierten Sprachen betrachten:

Turingmaschine:
TM sie die Menge von Sprachen, die durch Turingmaschinen akzeptiert werden.
nichtdeterministisch lineare Automaten:
NLBA sie die Menge von Sprachen, die durch nichtdeterministisch lineare Automaten akzeptiert werden.
nichtdeterministische / deterministisch Kellerautomaten:
NPDA / DPDA sie die Menge von Sprachen, die durch nichtdeterministische / deterministisch Kellerautomaten akzeptiert werden.
endliche Automaten:
EA sie die Menge von Sprachen, die durch endliche Automaten akzeptiert werden. (Wir kennen diese Menge als DA, NVA und NA.)

Desweiteren seien

reguläre Ausdrücke:
Reg sei die Menge von Sprachen, die durch reguläre Ausdrücke beschrieben werden können.
entscheidbare Sprachen:
Ent sei die Menge von Sprachen, die entscheidbar sind.
aufzählbare Sprachen:
Auf sei die Menge von Sprachen, die aufzählbar sind.

Dann ergibt sich folgend Betrachtung:
(LL=RR=Reg=EA) Ì (CF=NPDA=DPDA) Ì (CS=NLBA) Ì (Ent) Ì (CH=TM=Auf)

Wenn man neue Grammatiktypen oder andere Konzepte zur Definition von Sprachen einführt, dann gibt die Einordnung in die Chomsky-Hierarchie eine sehr genaue Vorstellung von der Mächtigkeit des Konzepts.

Dies alles wird jedoch auch noch Thema der nächsten Vorlesungen sein.