Grammatiken und die Chomsky-Hierarchie

Autoren: Pascal Lenzner und Martin Schirneck

In dieser Lehreinheit lernst du Grammatiken kennen. Genau wie Automaten sind Grammatiken eine Möglichkeit, formale Sprachen zu beschreiben. Einfach gesagt bestehen Grammatiken aus Ersetzungsregeln, mit denen man Schritt für Schritt ein Element der gewünschten Sprache aufbauen kann. Sie erlauben es uns, Strukturen in den erzeugten Sprachen zu entdecken und sie so in verschiedene Klassen einzusortieren: die sogenannte Chomsky-Hierarchie. Außerdem bilden Grammatiken die Grundlage für Parser sowohl in der Verarbeitung natürlicher Sprachen als auch für Programmiersprachen.

Grammatiken

Grammatiken geben Regeln an, wie ein Satz der Sprache aufgebaut ist. In der deutschen Sprache beispielsweise hat ein einfacher Satz die Struktur "Subjekt Prädikat Objekt." (beachte den Satzpunkt am Ende). Ein Subjekt wiederum kann dabei ein Personalpronomen wie Ich und Du (am Anfang des Satzes groß geschrieben) oder auch ein Name, Robotino oder Hasso, sein. Ein Pädikat ist ein gebeugtes Verb, z. B. schreibe, programmierst, lernst, sieht oder lehrt. Objekte, schließlich, sind häufig kurze Wortgruppen wie eine Lehreinheit, den Satz, die Anwendung, dieses Thema oder einen Baum.

In Kurzschreibweise erhält man daraus folgende Regeln:

• SATZ \(\to\) SUBJEKT PRÄDIKAT OBJEKT.
• SUBJEKT \(\to\) PRONOMEN \(\mid\) NAME
• PRONOMEN \(\to\) Ich \(\mid\) Du
• NAME \(\to\) Robotino \(\mid\) Hasso
• PRÄDIKAT \(\to\) schreibe \(\mid\) programmierst \(\mid\) lernst \(\mid\) sieht \(\mid\) lehrt
• OBJEKT \(\to\) eine Lehreinheit \(\mid\) den Satz \(\mid\) einen Parser \(\mid\) dieses Thema \(\mid\) einen Baum

Der senkrechte Strich bedeutet ›oder‹. Die Großschreibung dient dabei der Unterscheidung zwischen den Wortkategorien und den eigentlichen Worten. So hat die Kategorie SATZ in der Grammatik eine ganz andere Bedeutung als die Wortgruppe den Satz.

Mögliche Sätze in dieser Kunstsprache wären dann beispielsweise Ich schreibe eine Lehreinheit. oder Du programmierst einen Parser., aber auch so etwas wie Robotino lernst einen Baum. wäre korrekt. Umgekehrt ist Hasso lehrt. kein gültiger Satz, denn es fehlt das Objekt.

Findest du noch weitere Sätze?

Formale Definition

Eine formale Grammatik \(G\) ist ein 4-Tupel \(G = (N,T,P,S),\) sodass gilt:

• \(N\) ist die endliche Menge von Nichtterminalen,
• \(T\) ist die endliche Menge von Terminalen, wobei \(N \cap T = \emptyset,\)
• \(P\) ist eine endliche Menge von Produktionsregeln der Form \(\alpha \to \beta\) mit \(\alpha,\beta \in (N \cup T)^*\!,\)
  wobei \(\alpha\) mindestens ein Nichtterminal enthält,
• \(S \in N\) ist das Startsymbol.

Gelegentlich findet man auch die Definition \(G = (V,\Sigma,P,S),\) bei der die Menge der Terminale mit \(\Sigma\) und das gesamte Vokabular mit \(V \supsetneq \Sigma\) bezeichnet wird. Für die Produktionsregeln gilt dann \(P \subset_\text{fin} V^*{\setminus}\Sigma^* \times V^*\!.\) Die beiden Fassungen sind aber äquivalent.

Die Menge \(P\) kann manchmal sehr groß sein. Als Abkürzung für Regeln \(\alpha \to \beta,\) \(\alpha \to \gamma,\) \(\alpha \to \delta\) usw. mit derselben linken Seite schreibt man daher \(\alpha \to \beta \mid \gamma \mid \delta \mid \dots\) Das haben wir auch schon in dem Einführungsbeispiel so gemacht.

Ableitungen

Nichtterminale übernehmen in formalen Grammatiken die Rolle von Satzgliedern; die haben wir oben groß geschrieben und als Kategorien bezeichnet. Terminale dagegen sind die eigentlichen Worte. Wir wollen, dass unsere Sätze am Ende nur noch aus Terminalsymbolen bestehen, nach und nach müssen also alle Nichtterminalsymbole ersetzt werden. Um zu verstehen, wie dieser Ersetzungsprozess genau funktioniert, definieren wir die Anwendung von Produktionsregeln formal. Dafür benötigen wir den Begriff der Satzform und den der Ableitungsrelation. Eine Satzform ist ein Element aus \((N \cup T)^*\!,\) also eine endliche Zeichenkette aus Nichtterminal- und Terminalsymbolen. Die Variablen \(\alpha\) und \(\beta\) in der Definition oben bezeichnen also Satzformen. Beachte, dass auch das leere Wort \(\varepsilon\) immer eine Satzform ist, wenn auch eine ganz besondere.

Produktionsregeln aus \(P\) erlauben uns alte Satzformen durch neue zu ersetzen, aber nicht jede Regel ist auf jeden Satz anwendbar.

Ein Beispiel:
Nehmen wir die Satzform SUBJEKT PRÄDIKAT OBJEKT. in der Grammatik von oben. Dann können wir mit der Regel OBJEKT \(\to\) eine Lehreinheit den Satz SUBJEKT PRÄDIKAT eine Lehreinheit. erzeugen. Wir nennen das ableiten. Die Regel NAME \(\to\) Robotino ist dagegen nicht anwendbar, denn das Nichtterminal NAME kommt in dem Satz gar nicht vor.

Wir sagen, dass eine Satzform \(\alpha\) die Satzform \(\delta\) als Teilwort enthält, wenn es (ggf. leere) Satzformen \(\gamma\) und \(\gamma'\) gibt, so dass sich \(\alpha\) als \(\gamma\delta\gamma'\) schreiben lässt. Eine Produktionsregel \(\delta \to \eta\) ist genau dann auf \(\alpha\) anwendbar, wenn \(\alpha\) das Teilwort \(\delta\) hat. Jetzt haben wir alle Hilfsmittel zusammen, um Ableitungen sauber zu definieren:

• Für Satzformen \(\alpha,\beta \in (N \cup T)^*\) gilt \(\alpha \Rightarrow \beta,\) \(\alpha\) geht in einem Schritt in \(\beta\) über, falls es Satzformen \(\gamma,\gamma',\delta,\eta\) gibt, so dass \(\alpha = \gamma\delta\gamma'\) sowie \(\beta = \gamma\eta\gamma'\) gilt und \(\delta \to \eta\) eine Regel in \(P\) ist.
• Es gilt \(\alpha \Rightarrow^* \beta,\) d.h. es gibt eine Ableitung (Abfolge von Regelanwendungen) von \(\beta\) aus \(\alpha,\) falls \(\alpha\) in endlich vielen Schritten in \(\beta\) übergeht.

Nachdem wir nun wissen, wie wir von einer Satzform zur nächsten kommen, müssen wir nur noch festlegen, wo wir starten und wann wir aufhören.

• Die von einer Grammatik \(G = (N,T,P,S)\) erzeugte Sprache ist die Menge aller Satzformen, die sich aus dem Startsymbol \(S\) ableiten lassen und ausschließlich aus Terminalsymbolen bestehen, d. h.
  \(L(G) = \{\alpha \in T^* \mid S \Rightarrow^* \alpha\}.\)

Jetzt ist auch klar, warum Regeln auf der linken Seite immer mindestens ein Nichtterminal haben müssen: Wenn ich einmal eine Zeichenkette abgeleitet habe, die nur noch aus Terminalen besteht, muss ich sicher sein können, dass ich fertig bin. Dann ist nämlich garantiert keine Regel mehr anwendbar.

Beispiele

Wir verwenden zunächst wieder die Grammatik von oben. Wir wollen zeigen, dass Du lernst dieses Thema. ein Satz der erzeugten Sprache ist. Nach einer ersten Syntaxprüfung sehen wir, dass der Satz nur aus Terminalsymbolen besteht, die in der Grammatik vorkommen. Das gilt aber ja auch für Hasso lehrt., also müssen wir noch eine Ableitungsfolge angeben, die mit SATZ startet und in unserem Satz endet:

SATZ \(\Rightarrow\) SUBJEKT PRÄDIKAT OBJEKT. \(\Rightarrow\) PRONOMEN PRÄDIKAT OBJEKT. \(\Rightarrow\)
Du PRÄDIKAT OBJEKT. \(\Rightarrow\) Du lernst OBJEKT. \(\Rightarrow\) Du lernst dieses Thema.

Siehst du, welche Regeln bei den Übergängen angewendet wurden?

Als nächstes bauen wir eine Grammatik für gerade natürliche Zahlen. Gerade Zahlen enden immer auf eine gerade Ziffer, außerdem ist die Zahl \(0\) die einzige gerade Zahl, die auch mit der Ziffer \(0\) beginnt. Weitere Einschränkungen gibt es aber keine. Als Grammatik lässt sich das so schreiben:

\(G_\text{gerade} =(\{\)GZAHL, ZAHL, NNZ, GZ, ZIFFER\(\}, \{0,\dots,9\}, P,\)GZAHL\(),\)
wobei \(P\) die folgenden Produktionsregeln enthält

• GZAHL \(\to\) GZ \(\mid\) NNZ ZAHL GZ,
• ZAHL \(\to\) ZAHL ZIFFER \(\mid\) \(\varepsilon\),
• ZIFFER \(\to 0\) \(\mid\) NNZ,
• NNZ \(\to 1 \mid 2 \mid \dots \mid 9,\)
• GZ \(\to 0 \mid 2 \mid 4 \mid 6 \mid 8.\)

In der Regel ZAHL \(\to\) ZAHL ZIFFER kommt das Nichtterminal ZAHL sowohl auf der linken als auch auf der rechten Seite vor. Das ermöglicht eine Art Rekursion, so dass beliebig lange Zahlen erzeugt werden können. Die Regel ZAHL \(\to \varepsilon\) mit dem leeren Wort auf der rechten Seite sorgt dafür, dass diese Rekursion auch irgendwann einmal abbricht.

Findest du Ableitungen für \(2\) und für \(1024?\) Auch für \(2199023255552?\) Warum lässt sich \(373\) nicht ableiten? Was ist mit \(004?\)

Das dritte Beispiel ist sehr kurz aber dafür etwas kniffliger:

Die Grammatik hat nur drei Regeln S \(\to\) SS, S \(\to\) (S) und S \(\to \varepsilon\).
Das einzige Nichtterminal S ist natürlich das Startsymbol.

Versuche herauszufinden, welche Sprache die Grammatik beschreibt. Tipp: Die Lösung findest du hier.

Die Chomsky-Hierarchie

Grammatiken sind sehr mächtige Werkzeuge, die ganz verschiedenartige Sprachen erzeugen können. Man kann bereits an der Grammatik selbst — vor allem an den Regeln natürlich — viele Eigenschaften der zugehörigen Sprache ablesen. Die Klassifizierung von Grammatiken nach der Komplexität ihrer Regeln führt so zu einer Klassifizierung der formalen Sprachen selbst.

Das bekannteste Schema für eine solche Klassifizierung ist die Chomsky-Hierarchie. Sie ist benannt nach dem amerikanischen Linguisten Noam Chomsky. Die Chomsky-Hierarchie hat vier Stufen: Typ 0 bis Typ 3. Je höher der Typ, desto eingeschränkter sind dabei die Regeln. Man nennt eine formale Sprache ebenfalls vom Typ \(n\), wenn sie von einer Typ-\(n\)-Grammatik erzeugt wird.

Typ 0 — Unbeschränkte Grammatiken

Wir gehen immer von einer Grammatik \(G=(N,T,P,S)\) aus.

• Die Grammatik \(G\) ist vom Typ 0 oder unbeschränkt, wenn alle Regeln in \(P\) von der Form \((N \cup T)^*N(N \cup T)^* \to (N \cup T)^*\) sind.

Die Definition sieht erst einmal kompliziert aus, sie besagt aber nur, dass auf der linken Seite jeder Regel mindestens ein Nichtterminalsymbol stehen muss. Das haben wir aber ja sowieso von Anfang an gefordert, also sind alle Grammatiken mindestens vom Typ 0.

Es lässt sich zeigen, dass Typ-0-Grammatiken genau diejenigen Sprachen erzeugen können, die von Turingmaschinen akzeptiert werden! Mit anderen Worten: Sie erzeugen genau die rekursiv aufzählbaren Sprachen. Eine echte Typ-0-Sprache, die also keinen höheren Typ hat, ist das Halteproblem. Eine vollständige Grammatik anzugeben würde hier aber zu weit führen.

Typ 1 — Kontextsensitive Grammatiken

Das Problem bei unbeschränkten Grammatiken ist, dass beim Ableitungsprozess die Länge der Satzform wild hin und her springen kann, insbesondere kann sie unterwegs kürzer werden. Dadurch kann man nie wissen, ob man bereits alle ableitbaren Satzformen einer bestimmten Länge gefunden hat. Um das zu verhindern, wurden die kontextsensitiven Grammatiken eingeführt.

• Die Grammatik \(G\) ist vom Typ 1 oder kontextsensitiv, wenn sie vom Typ 0 ist und zusätzlich für alle Regeln \(\alpha \to \beta\) in \(P\) gilt, dass \(|\alpha| \le |\beta|\).

Nun hat man aber ein neues Problem: Wie soll man das leere Wort aus dem Startsymbol S ableiten, wenn Satzformen immer nur länger werden dürfen? Dafür braucht man noch eine Sonderregel:

• In Typ-1-Grammatiken ist die Produktionsregel S \(\to \varepsilon\) erlaubt; aber nur, wenn das Startsymbol S auf keiner rechten Seite einer Regel aus \(P\) steht.

Die kontextsensitiven Sprachen sind genau diejenigen, die von sogenannten nichtdeterministischen linear beschränkten Automaten (LBAs) akzeptiert werden. LBAs sind Turingmaschinen, die nie den Bereich verlassen, in dem ursprünglich das Eingabewort stand. Es ist ein offenes Problem der Theoretischen Informatik, ob schon die deterministischen LBAs genügen, um alle kontextsensitiven Sprachen zu erkennen. Alle Typ-1-Sprachen (und die höheren Typs) sind entscheidbar.

Eine echte Typ-1-Sprache ist \(\{a^n b^n c^n \mid n \ge 0\}.\) Sie wird bspw. von der Grammatik mit den folgenden Regeln erzeugt:

• S \(\to\) S' \(\mid\) \(\varepsilon\),
• S' \(\to\) \(a\)S'B\(c\) \(\mid\) \(abc,\)
• \(c\)B \(\to\) B\(c,\)
• \(b\)B \(\to\) \(bb.\)

Das Nichtterminal S' braucht man nur, damit die Bedingung der Sonderregel erfüllt ist. An dem Beispiel sieht man auch schön, warum die Grammatik kontextsensitiv heißt: Das Nichtterminal B wird mal zur Satzform B\(c\) und mal zu \(bb\), je nachdem ob B im Kontext \(c\) oder \(b\) steht.

Typ 2 — Kontextfreie Grammatiken

Beim Ableiten in Typ-1-Grammatiken muss man immer aufpassen, dass das Nichtterminal auch im richtigen Kontext steht. Das Erzeugen von Sätzen ist viel leichter, wenn die Grammatik kontextfrei ist.

• Eine Grammatik \(G\) ist vom Typ 2 oder kontextfrei, wenn sie vom Typ 1 ist und zusätzlich auf der linken Seite jeder Regel aus \(P\) genau ein Nichtterminal steht. Sie sind also von der Form \(N \to (N \cup T)^*\!.\)
• Regeln X \(\to \varepsilon\) sind für beliebige Nichtterminale \(X \in N\) zulässig.

Die kontextfreien Sprachen sind genau diejenigen, die von nichtdeterministischen Kellerautomaten (PDAs) akzeptiert werden. Hier weiß man bereits, dass deterministische Automaten nicht ausreichen. Im Bezug auf Grammatiken ergibt der Begriff kontextfrei viel mehr Sinn als bei den PDAs.

Eine echte Typ-2-Sprache ist \(\{a^n b^n \mid n \ge 0\}.\) Sie wird von der Grammatik mit den beiden Regeln

• S \(\to\) \(a\)S\(b,\)
• S \(\to\) \(\varepsilon\)

erzeugt.

Kommt dir diese Grammatik bekannt vor? Findest du noch mehr kontextfreie Grammatiken in dieser Lehreinheit?

Typ 3 — Reguläre Grammatiken

Man hat die einfachste Form der Ableitung, wenn man den gewünschten Satz (als Terminalfolge) Schritt für Schritt von links nach rechts aufbauen kann. Genau das erlauben die regulären Grammatiken.

• Eine Grammatik \(G\) ist vom Typ 3 oder regulär, wenn sie vom Typ 2 ist und zusätzlich jede Regel aus \(P\) eine der Formen \(N \to T\), \(N \to TN\) oder \(N \to \varepsilon\) hat.

Die regulären Sprachen sind genau diejenigen, die von endlichen Automaten (deterministisch, wie auch nichtdeterministisch) akzeptiert werden. Die regulären Sprachen bilden gewissermaßen die einfachste Klasse von formalen Sprachen überhaupt.

Eine echte Typ-3-Sprache ist \(\{a^n \mid n \ge 0\}.\) Erzeugt wird sie wird von der Grammatik

• S \(\to\) \(a\)S \(\mid\) \(\varepsilon\).

Die Grammatik, die wir uns ganz am Anfang definiert haben (Hasso sieht dieses Thema.) ist zwar selbst nicht regulär, aber sie erzeugt eine reguläre Sprache. Das sieht man schon daran, dass man nur endlich viele Sätze ableiten kann; endliche Mengen sind immer regulär. Findest du auch eine reguläre Grammatik für dieses Beispiel?

Was haben wir gelernt?

1. Grammatiken sind eine Möglichkeit, formale Sprachen zu beschreiben.
2. Grammatiken geben Ersetzungsregeln an, mit denen schrittweise Sätze abgeleitet werden können.
3. Die Chomsky-Hierarchie klassifiziert sowohl Grammatiken als auch die erzeugten Sprachen.
4. Die Stufen der Chomsky-Hierarchie passen jeweils genau auf eine bestimmte Automatenklasse.