Chomsky-Hierarchie
Der amerikanische Sprachwissenschaftler A. Noam Chomsky (*07.12.1928) untersuchte u.a.
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
Grammatiken:
Diese
Grammatik ohne jegliche Einschränkung erzeugt eine Menge von Sprachen, die hier mit CH bezeichnet wird.
Diese
Grammatik ist kontextsensitiv und erzeugt eine Menge von Sprachen, die hier mit CS bezeichnet wird.
Diese
Grammatik ist kontextfrei und erzeugt eine Menge von Sprachen, die hier mit CF bezeichnet wird.
Diese
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)
Operation | Typ 0 | Typ 1 | Typ 2 | Typ 3 |
Vereinigung | ja | ja | ja | ja |
Schnitt | ja | ja | nein | ja |
Komplement | nein | ja | ja | nein |
Verkettung | ja | ja | ja | ja |
*-Bildung | ja | ja | ja | ja |
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.