Kontextfreie Grammatik
Kontextfreie Grammatiken beschreiben verschachtelte Strukturen wie Klammern und Programmblöcke. Dafür reichen reguläre Sprachen nicht aus.
Definition
Eine kontextfreie Grammatik ist eine formale Grammatik [math]\displaystyle{ G = (N, T, P, S) }[/math], deren Regeln links genau ein Nichtterminal haben:
- [math]\displaystyle{ A \to \beta }[/math] mit [math]\displaystyle{ A \in N }[/math] und [math]\displaystyle{ \beta \in (N \cup T)^* }[/math]
Die rechte Seite [math]\displaystyle{ \beta }[/math] ist eine beliebige, auch leere Folge aus Nichtterminalen und Terminalen. Weil links nur ein einzelnes Nichtterminal steht, ersetzt die Regel es unabhängig vom Umfeld, dem Kontext. Die erzeugten Sprachen heißen kontextfreie Sprachen. Sie bilden Typ 2 der Chomsky-Hierarchie. Passende Automaten sind die Kellerautomaten.
Links- und Rechtsableitung
Enthält eine Zeichenfolge mehrere Nichtterminale, lässt sich die Reihenfolge der Ersetzungen wählen. Zwei Reihenfolgen haben eigene Namen:
- Die Linksableitung ersetzt in jedem Schritt das am weitesten links stehende Nichtterminal.
- Die Rechtsableitung ersetzt in jedem Schritt das am weitesten rechts stehende Nichtterminal.
Ableitungsbaum
Ein Ableitungsbaum (auch Syntaxbaum) zeigt, wie ein Wort aus dem Startsymbol entsteht:
- Die Wurzel ist das Startsymbol.
- Jeder innere Knoten ist ein Nichtterminal. Seine Kinder sind, von links nach rechts, die Symbole der rechten Seite der angewendeten Regel. Bei einer Regel [math]\displaystyle{ A \to \varepsilon }[/math] ist [math]\displaystyle{ \varepsilon }[/math] das einzige Kind.
- Die Blätter ergeben von links nach rechts gelesen das Wort.
Zu jedem Ableitungsbaum gibt es genau eine Linksableitung und genau eine Rechtsableitung. Sie unterscheiden sich nur in der Reihenfolge, in der die Knoten ersetzt werden. Auch der Artikel Syntax erklärt den Ableitungsbaum am Satzbau.
Mehrdeutigkeit
Eine kontextfreie Grammatik ist mehrdeutig, wenn es für mindestens ein Wort zwei verschiedene Ableitungsbäume gibt. Zwei Ableitungen desselben Baums, etwa eine Links- und eine Rechtsableitung, sind keine Mehrdeutigkeit.
Bei einem mehrdeutigen Wort legt die Grammatik nicht fest, welche Struktur gemeint ist. Mehrdeutigkeit ist eine Eigenschaft der Grammatik, nicht der Sprache: Dieselbe Sprache kann sowohl durch eine mehrdeutige als auch durch eine eindeutige Grammatik beschrieben werden.
Grenzen regulärer Sprachen
Ein DEA hat endlich viele Zustände und kann deshalb nicht beliebig weit zählen. Der Grund:
- Hat der DEA [math]\displaystyle{ n }[/math] Zustände, durchläuft er beim Lesen von [math]\displaystyle{ n }[/math] Zeichen [math]\displaystyle{ n + 1 }[/math] Zustände. Also wiederholt sich ein Zustand (Schubfachprinzip), und es entsteht eine Schleife.
- Die Schleife lässt sich beliebig oft durchlaufen. Nach jedem Durchlauf ist der Automat im selben Zustand.
- Der DEA kann deshalb nicht mehr unterscheiden, wie oft die Schleife durchlaufen wurde. Die gelesene Anzahl geht verloren.
Verlangt eine Sprache, dass eine unbegrenzte Anzahl mitgezählt wird, erkennt kein DEA sie: Die Sprache ist nicht regulär. Eine kontextfreie Grammatik kann solche Anzahlen vergleichen, weil eine Regel das Nichtterminal in der Mitte der rechten Seite stehen lassen kann ([math]\displaystyle{ A \to \beta_1 A \beta_2 }[/math]). Dann entstehen links und rechts davon gleichzeitig neue Zeichen.
Jede reguläre Sprache ist kontextfrei, denn reguläre Regeln haben auch die Form [math]\displaystyle{ A \to \beta }[/math]. Die Umkehrung gilt nicht.
Pumping-Lemma
Das Pumping-Lemma beschreibt eine Eigenschaft, die jede reguläre Sprache hat. Zu jeder regulären Sprache [math]\displaystyle{ L }[/math] gibt es eine Zahl [math]\displaystyle{ n \geq 1 }[/math], sodass jedes Wort [math]\displaystyle{ w \in L }[/math] mit [math]\displaystyle{ |w| \geq n }[/math] eine Zerlegung [math]\displaystyle{ w = xyz }[/math] hat mit
- [math]\displaystyle{ |xy| \leq n }[/math],
- [math]\displaystyle{ |y| \geq 1 }[/math] und
- [math]\displaystyle{ xy^iz \in L }[/math] für alle [math]\displaystyle{ i \geq 0 }[/math].
Der Teil [math]\displaystyle{ y }[/math] lässt sich also beliebig oft wiederholen („aufpumpen“) oder weglassen, ohne dass das Wort die Sprache verlässt.
Das Lemma dient dem Nachweis, dass eine Sprache nicht regulär ist. Es ist nur eine notwendige Bedingung: Erfüllt eine Sprache das Lemma, folgt daraus nicht, dass sie regulär ist. Der Nachweis verläuft so:
- Annahme: [math]\displaystyle{ L }[/math] ist regulär. Dann gibt es eine Zahl [math]\displaystyle{ n }[/math] wie im Lemma.
- Ein Wort [math]\displaystyle{ w \in L }[/math] mit [math]\displaystyle{ |w| \geq n }[/math] wählen, abhängig von [math]\displaystyle{ n }[/math].
- Das Lemma liefert eine Zerlegung [math]\displaystyle{ w = xyz }[/math], die nicht frei wählbar ist. Wegen [math]\displaystyle{ |xy| \leq n }[/math] liegt [math]\displaystyle{ y }[/math] im vorderen Teil von [math]\displaystyle{ w }[/math].
- Für jede solche Zerlegung ein [math]\displaystyle{ i }[/math] mit [math]\displaystyle{ xy^iz \notin L }[/math] zeigen. Das widerspricht dem Lemma. Also ist [math]\displaystyle{ L }[/math] nicht regulär.
Beispiele
Klammerausdrücke ableiten
Die Grammatik mit dem Startsymbol [math]\displaystyle{ S }[/math] und den Terminalen ( und ) erzeugt korrekt geklammerte Ausdrücke. Ihre Regeln:
- [math]\displaystyle{ S \to (S)S \mid \varepsilon }[/math]
Die Regel [math]\displaystyle{ S \to (S)S }[/math] setzt ein Klammerpaar, in dem ein Ausdruck steht, und lässt einen weiteren Ausdruck folgen. Die Regel [math]\displaystyle{ S \to \varepsilon }[/math] beendet die Ableitung. Das Wort ()() lässt sich auf zwei Arten ableiten.
Die Linksableitung ersetzt immer das am weitesten links stehende [math]\displaystyle{ S }[/math]:
- [math]\displaystyle{ S \Rightarrow (S)S \Rightarrow ()S \Rightarrow ()(S)S \Rightarrow ()()S \Rightarrow ()() }[/math]
Die Rechtsableitung ersetzt immer das am weitesten rechts stehende [math]\displaystyle{ S }[/math]:
- [math]\displaystyle{ S \Rightarrow (S)S \Rightarrow (S)(S)S \Rightarrow (S)(S) \Rightarrow (S)() \Rightarrow ()() }[/math]
Der Ableitungsbaum zeigt die Struktur. Die Wurzel [math]\displaystyle{ S }[/math] hat die Kinder (, [math]\displaystyle{ S }[/math], ) und [math]\displaystyle{ S }[/math]. Das erste innere [math]\displaystyle{ S }[/math] wird zu [math]\displaystyle{ \varepsilon }[/math]. Das letzte [math]\displaystyle{ S }[/math] hat wieder die Kinder (, [math]\displaystyle{ S }[/math], ) und [math]\displaystyle{ S }[/math], und beide [math]\displaystyle{ S }[/math] werden zu [math]\displaystyle{ \varepsilon }[/math]. Die Blätter ergeben von links nach rechts ()(). Links- und Rechtsableitung gehören zu demselben Baum.
Nichtzugehörigkeit begründen
Gehört das Wort (() zur Sprache der Grammatik [math]\displaystyle{ S \to (S)S \mid \varepsilon }[/math]? Nein. Die Regel [math]\displaystyle{ S \to (S)S }[/math] erzeugt je eine öffnende und eine schließende Klammer, die Regel [math]\displaystyle{ S \to \varepsilon }[/math] keine. Jede Ableitung erzeugt deshalb gleich viele ( und ). Das Wort (() hat zwei ( und nur eine ). Es gehört nicht zur Sprache.
Mehrdeutigkeit nachweisen
Bedingte Anweisungen lassen sich mit einer Grammatik beschreiben: i steht für if (...) (wenn), e für else (sonst) und a für eine Anweisung. Die Regeln:
- [math]\displaystyle{ S \to iS \mid iSeS \mid a }[/math]
Die Regel [math]\displaystyle{ S \to iS }[/math] beschreibt ein if ohne else, die Regel [math]\displaystyle{ S \to iSeS }[/math] ein if mit else. Das Wort iiaea hat zwei Ableitungsbäume:
- Linker Baum: Die Wurzel verwendet [math]\displaystyle{ S \to iS }[/math], das innere [math]\displaystyle{ S }[/math] verwendet [math]\displaystyle{ S \to iSeS }[/math]. Das
elsegehört zum innerenif. - Rechter Baum: Die Wurzel verwendet [math]\displaystyle{ S \to iSeS }[/math], das erste [math]\displaystyle{ S }[/math] darunter verwendet [math]\displaystyle{ S \to iS }[/math]. Das
elsegehört zum äußerenif.
Das Wort hat zwei verschiedene Bäume, die Grammatik ist also mehrdeutig. Java legt zusätzlich fest: Das else gehört zum nächstgelegenen if davor. Das entspricht dem linken Baum.
Nicht-Regularität begründen
Die Sprache [math]\displaystyle{ L = \{0^n 1^n \mid n \geq 1\} }[/math] ist nicht regulär:
- Annahme: Ein DEA mit [math]\displaystyle{ k }[/math] Zuständen erkennt [math]\displaystyle{ L }[/math].
- Das Wort [math]\displaystyle{ 0^k 1^k }[/math] gehört zu [math]\displaystyle{ L }[/math]. Beim Lesen von [math]\displaystyle{ 0^k }[/math] durchläuft der DEA [math]\displaystyle{ k + 1 }[/math] Zustände. Ein Zustand wiederholt sich (Schubfachprinzip). Die Schleife dazwischen hat die Länge [math]\displaystyle{ m \geq 1 }[/math].
- Der DEA kann die Schleife einmal mehr durchlaufen. Nach [math]\displaystyle{ 0^{k+m} }[/math] ist er im selben Zustand wie nach [math]\displaystyle{ 0^k }[/math].
- Danach liest er [math]\displaystyle{ 1^k }[/math] und endet im selben Endzustand wie bei [math]\displaystyle{ 0^k 1^k }[/math]. Er akzeptiert also [math]\displaystyle{ 0^{k+m} 1^k }[/math].
- Dieses Wort hat mehr Nullen als Einsen und gehört nicht zu [math]\displaystyle{ L }[/math]. Das ist ein Widerspruch. Also gibt es keinen DEA für [math]\displaystyle{ L }[/math].
Pumping-Lemma anwenden
Für dieselbe Sprache [math]\displaystyle{ L = \{0^n 1^n \mid n \geq 1\} }[/math] gilt:
- Annahme: [math]\displaystyle{ L }[/math] ist regulär, und [math]\displaystyle{ n }[/math] ist die Zahl aus dem Pumping-Lemma.
- Gewählt wird [math]\displaystyle{ w = 0^n 1^n }[/math]. Es gilt [math]\displaystyle{ w \in L }[/math] und [math]\displaystyle{ |w| = 2n \geq n }[/math].
- Das Lemma liefert eine Zerlegung [math]\displaystyle{ w = xyz }[/math] mit [math]\displaystyle{ |xy| \leq n }[/math] und [math]\displaystyle{ |y| \geq 1 }[/math]. Die ersten [math]\displaystyle{ n }[/math] Zeichen von [math]\displaystyle{ w }[/math] sind Nullen. Also besteht [math]\displaystyle{ y }[/math] nur aus Nullen und enthält mindestens eine.
- Für [math]\displaystyle{ i = 2 }[/math] hat [math]\displaystyle{ xy^2z }[/math] mehr als [math]\displaystyle{ n }[/math] Nullen, aber nur [math]\displaystyle{ n }[/math] Einsen. Das Wort gehört nicht zu [math]\displaystyle{ L }[/math]. Das widerspricht [math]\displaystyle{ xy^iz \in L }[/math] für alle [math]\displaystyle{ i \geq 0 }[/math]. Also ist [math]\displaystyle{ L }[/math] nicht regulär.