Chomsky Hierarchie
In diesem Beitrag wird dir die Chomsky Hierarchie einfach erklärt! Hier erfährst du alles über die Typ-0-Grammatik, die Typ-1-Grammatik, die Typ-2-Grammatik und die Typ-3-Grammatik inklusive jeweiligen Chomsky Hierarchie Beispielen. Zum Schluss zeigen wir dir noch den Zusammenhang mit formalen Sprachen.
Wenn du nicht so viel Text lesen willst, findest du in unserem Video alle wichtigen Informationen inklusive Beispiel kurz und knapp zusammengefasst!
Inhaltsübersicht
Chomsky Hierarchie – Definition
Die Chomsky Hierarchie stellt in der theoretischen Informatik eine Hierarchie von Klassen formaler Grammatiken dar, welche formale Sprachen erzeugen. Dabei wird zwischen vier verschiedenen Typen der Grammatik (Hierarchiestufen) unterschieden, die nach den Einschränkungen ihrer Produktion handeln.
Chomsky Hierarchie einfach erklärt
Die Chomsky Hierarchie (englisch chomsky hierarchy) wurde von dem Sprachwissenschaftler Noam Chomsky und dem Mathematiker Marcel Schützenberger 1956 entwickelt, weswegen sie auch ab und an als Chomsky-Schützenberger-Hierarchie bezeichnet wird. Der ursprüngliche Grundgedanke war dabei, für die natürliche Sprache eine mathematische Beschreibungsform zu finden.
Formale Grammatiken
Formale Grammatiken beschreiben und erzeugen durch Symbole und Regeln formale Sprachen. Die Regeln definieren dabei, wie neue Symbole aus bereits bestehenden entstehen können. Bei den Symbolen unterscheidet man zwischen terminalen und nichtterminalen:
Nichtterminale Symbole können durch andere Symbole ersetzt werden, während terminale Symbole unveränderlich sind.
Heißt man erkennt die Symbole an sogenannten Produktionsregeln. Diese Regeln beschreiben, aus welchen Zeichen welche anderen Zeichen entstehen können.
Hier ein Beispiel:
Das S ist hierbei ein nichtterminales Symbol, da es entweder durch „aSa“ oder durch „b“ ersetzt werden kann. Die Zeichen „a“ und „b“ sind nicht mehr ersetzbar, also werden sie als terminal bezeichnet.
Hierarchiestufen
Die Chomsky-Hierarchie teilt nun formale Grammatiken in vier verschiedene Klassen ein, die sich in der Einschränkung der Produktionsregeln der verschiedenen Typen unterscheiden. Hierbei schränkt Typ-0 die Sprache überhaupt nicht ein, während Typ-3 die Grammatik sehr stark einschränkt.
Typ-O-Grammatik
Die Typ-0-Grammatik wird auch Chomsky-Grammatik oder Phasenstrukturgrammatik genannt. Allgemein kann man sagen, dass alle formalen Grammatiken mindestens vom Typ-0 sind, da hier keine Einschränkungen gestellt werden. Es kann also aus jedem Wort ein beliebiges anderes Wort entstehen.
Mit Typ-0-Grammatiken können rekursiv aufzählbare Sprachen erzeugt werden. Das heißt, dass die, auf die Sprache ausgelegte, Turingmaschine nur dann terminiert – und damit ein Wort akzeptiert – wenn es in der Sprache liegt.
Typ-1-Grammatik
Weiter geht es mit Typ-1-Grammatiken, auch kontextsensitive Grammatiken genannt. Sie erweitern die Typ-0-Grammatik um eine Längenbeschränkung. Diese Beschränkung sagt aus, dass bei einer Produktionsregel
immer gelten muss, dass die Länge von 
mindestens der Länge von 
entspricht.
Es gibt eine einzige Ausnahme:
aus einem Symbol S darf das leere Wort 
gebildet werden.
Die Typ-1-Grammatiken erzeugen kontextsensitive Sprachen. Eine nichtdeterministische, linear beschränkte Turingmaschine – also eine Turingmaschine, deren Band durch die Länge beschränkt ist – kann diese Sprache erkennen.
Typ-2-Grammatik
Kommen wir nun zu Typ-2 , also den kontextfreien, Grammatiken. Diese sind zusätzlich dadurch eingeschränkt, dass jede Regel der Grammatik auf der linken Seite genau ein nichtterminales Symbol, und auf der rechten Seite eine beliebige Kombination aus terminalen und nichtterminalen Symbolen enthalten muss. Die Kombination muss hierbei immer mindestens ein Element enthalten.
Typ-3-Grammatik
Zu guter Letzt widmen wir uns den Typ-3-Grammatiken, auch reguläre Grammatiken genannt. Sie sind im Vergleich zu Typ-2-Grammatiken zusätzlich dadurch eingeschränkt, dass auf der rechten Seite der Produktionsregeln genau ein Terminalsymbol sein muss und optional ein Nichtterminalsymbol sein kann. Je nachdem, auf welcher Seite des Terminalsymbols das nichtterminale Symbol ist, spricht man von einer linksregulären oder einer rechtsregulären Grammatik.
Typ-3-Grammatiken erzeugen die regulären Sprachen. Endliche Automaten
erkennen diese Sprachen.
Wenn du mehr zu Endlichen Automaten erfahren willst, findest du hier
eine ganze Videoreihe zum Thema.
Chomsky Hierarchie Beispiele
Es folgen Chomsky Hierarchie Beispiele für die verschiedenen Hierarchiestufen.
Beispiel – Typ-0-Grammatik
Als erstes ein Beispiel zur Typ-0-Grammatik:
Hier kann also ohne Probleme aus jedem Wort irgendein neues Wort entstehen.
Beispiel – Typ-1-Grammatik
Hier siehst du zwei gültige Typ-1-Grammatiken. Das Beispiel auf der rechten Seite dagegen stellt keine gültige Typ-1 Grammatik dar, denn hier ist Omega 1 länger als Omega 2.
Gültig:
Ein ungültiges Beispiel wäre:
Beispiel – Typ-2-Grammatik
Nun zum Beispiel der Typ-2-Grammatik: Links steht jeweils genau ein nichtterminales Symbol und rechts eine beliebige Kombination aus terminalen und nichtterminalen Symbolen.
Gültig:
Ungültig für eine Typ-2 Grammatik wären beispielsweise folgende Produktionsregeln, da auf der linken Seite mehr als ein nichtterminales Symbol steht.
Ungültig:
Beispiel – Typ-3-Grammatik
Als letztes folgt nun ein Beispiel für die Typ-3-Grammatik:
Hier gilt: A und B sind nichtterminal, a ist terminal.
Chomsky Hierarchie – formale Sprachen
Die Chomsky-Hierarchie ist nicht nur auf Grammatiken, sondern auch auf formale Sprachen anwendbar. Eine formale Sprache gehört genau dem Typen an, dem die Grammatik angehört, welche die Sprache erzeugt. Für die Sprache L des Typen i schreibt man dann:
Die höheren Grammatiken beinhalten die Niedrigeren. Heißt also zum Beispiel, dass Typ-3 nur ein Zusatz zur Typ-2-Grammatik ist. Das wird an dieser Grafik deutlich:
Die reguläre Sprache hierbei der kleinste Teil. Und bezüglich der Mengen wird sichtbar, dass die höheren Sprachen Teilmengen der niedrigeren sind. Formal sieht das also so aus:
ist eine Teilmenge von 
und so weiter.