Theoretische Informatik

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.

Chomsky Hierarchie
direkt ins Video springen
Chomsky Hierarchie

Hier ein Beispiel:

S\ \rightarrow aSa
S\ \rightarrow b

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

\omega_1\rightarrow\omega_2 immer gelten muss, dass die Länge von \omega_2 mindestens der Länge von \omega_1 entspricht.

Es gibt eine einzige Ausnahme:

aus einem Symbol S darf das leere Wort \varepsilon gebildet werden.

S\ \rightarrow\varepsilon

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:

\alpha\rightarrow\beta
abcdeNabcde\ \rightarrow\ aNa

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:

Nab\ \rightarrow Naab
aNNa\ \rightarrow abNb

Ein ungültiges Beispiel wäre:

aaNNaa\ \rightarrow aNa

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:

A\ \rightarrow BC\bigmB\ \rightarrow abCabA

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:

AABBCC\ \rightarrow aaBa
aB\ \rightarrow abCabA

Beispiel – Typ-3-Grammatik

Als letztes folgt nun ein Beispiel für die Typ-3-Grammatik:

A\ \rightarrow aB\ \ rechtsregulär
A\ \rightarrow Ba\ \ \ \ linksregulär

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:

L \in \mathcal{L}_i

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:

Chomsky Hierarchie Formale Sprachenn
direkt ins Video springen
Chomsky Hierarchie – Formale Sprachen

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:

\mathcal{L}_3\subset \mathcal{L}_2\subset \mathcal{L}_1\subset \mathcal{L}_0

\mathcal{L}_3 ist eine Teilmenge von \mathcal{L}_2 und so weiter.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.