6. Allgemeine Grammatiken

Wir haben nun ausführlich über kontextfreie Grammatiken gesprochen und auch Sprachen gesehen, die nicht mit kontextfreien Grammatiken zu beschreiben (und somit auch nicht mit Parsern oder allgemein mit Kellerautomaten) zu entscheiden sind. Da stellen sich die folgenden Fragen:

Wie mann man die Definition kontextfreier Grammatiken sinnvoll erweitern, so dass sie beispielsweise auch Sprachen wie $\{a^n b^n c^n \ | \ n \geq 0\}$ umfassen?
Gibt es eine natürliche Barriere, jenseits derer es keinen vernünftigen Begriff des "Beschreiben könnens" gibt? Oder kann man immer noch allgemeinere Regelwerke zulassen?
Gibt es für die (noch zu definierende) allgemeinere Art von Grammatiken auch eine Art Automat, so wie die endlichen Automaten für die regulären Grammatiken und die Kellerautomaten für die kontextfreien?

Punkt 1 werden wir in diesem Kapitel diskutieren. Punkt 2 und 3 werden Gegenstand des nächsten Kapitels sein, in welchem wir die Turing-Maschinen einführen.

Allgemeine formale Grammatiken

Definition (formale Grammatik) Eine formale Grammatik ist gegeben durch ein endliches Alphabet $\Sigma$ aus Terminalsymbolen, einer endlichen Menge $\N$ von Nichtterminalen, einem Startsymbol $S \in N$ und einer endlichen Menge an Produktionen \begin{align*} \alpha \rightarrow \beta \end{align*} wobei $\beta \in (\Sigma \cup \Gamma)^*$ und $\alpha \in (\Sigma \cup \Gamma)^* \setminus \Sigma^*$. Letzeres bedeutet einfach, dass die linke Seite $\alpha$ mindestens ein Nichtterminal enthalten muss.

Die Definition formaler Grammatik umschließt offensichtlich die der kontextfreien: sie verbietet nicht, dass alle linken Seiten $\alpha$ aus genau einem Nichtterminal bestehen; in diesem Falle hätten wir eine kontextfreie Grammatik. Sie verbietet auch nicht, dass zusätzlich alle rechten Seiten $\beta \in \Sigma^* \times N \cup \Sigma^*$ sind, also höchstens ein Nichtterminal enthalten, welches ganz rechts stehen muss. In diesem Falle würde es sich um eine reguläre Grammatik handeln.

Definition (Ableitung und erzeugte Sprache). Sei $G$ eine formale Grammtik und $\gamma_1, \gamma_2 \in (\Sigma\cup N)^* $ zwei Wortformen. Wir schreiben $\gamma_1 \Step{} \gamma_2$, wenn wir \begin{align*} \gamma_1 & = u \alpha v \\ \gamma_2 & = u \beta v \end{align*} schreiben können für Wortformen $u,v$, sodass $\alpha \rightarrow \beta$ eine Produktion von $G$ ist.

Beispiel Betrachten wir die allgemeine Grammatik mit Terminalalphabet $\Sigma = \{a,b,c\}$, Nichtterminalsymbolen $N = \{S, A, B, C\}$, Startsymbol $S$ und den Produktionen \begin{align*} S & \step{1} ABCS \ | \ \epsilon \\ AB & \step{2} BA \\ BA & \step{3} AB \\ AC & \step{4} CA \\ CA & \step{5} AC \\ BC & \step{6} CB \\ CB & \step{7} BC \\ A & \step{8} a \\ B & \step{9} b \\ C & \step{10} c \end{align*}

Nun schauen wir uns eine Beispielableitung an:

\begin{align*} S \Step{1} ABCS \Step{1} ABCABCS \Step{2} ABCABC \Step{5} ABACBC \Step{3} AABCBC \Step{8,8,9,9,10,10}^* aabcbc \end{align*}

Die obige Beispielableitung illustriert, dass allgemeine formale Grammatiken etwas können, das kontextfreie Grammatiken nicht bieten konnten: das Vertauschen von Symbolen. Das mag nicht als besonders viel erscheinen, wird sich aber als Game Changer herausstellen.

Sobald wir eine Wortform erreicht haben, die nur aus Terminalsymbolen besteht (also ein Wort geworden ist), muss unsere Ableitung aufhören: wir können keine weitere Produktion anwenden, da jede linke Seite mindestens ein Nichtterminal enthält. Diese Einschränkung in der Definition allgemeiner formaler Grammatiken ist nicht wirklich notwenig, sie macht Dinge allerdings klar, wo eine Ableitung zu Ende ist / sein muss. Es handelt sich also gewissermaßen um das Gegenteil von Syntax-Antizucker (mir ist gerade keine Substanz eingefallen, deren Geschmack universell als abstoßend empfunden wird). Wir können Grammatiken, die verbotene Produktionen der Form $\alpha \rightarrow \beta$ mit $\alpha \in \Sigma^*$ enthalten, immer "auf Linie" bringen, indem wir jedes Terminalsymbol $x$ in den Produktionen durch ein neues Nichtterminal $X$ ersetzen und schließlich Produktionen $X \rightarrow x$ einführen.

Beispiel Versuchen wir nun, eine allgemeine formale Grammatik für die Sprache \begin{align*} L = \{a^nb^nc^n \ | \ n \geq 0\} \end{align*} zu erstellen. Wir haben ja bereits gesehen, dass es zu dieser Sprache keine kontextfreie Grammatik gibt. Als ersten Versuch kopieren wir die obige Grammatik, allerdings lassen wir nur die Vertauschungsregeln zu, die die Buchstaben in die richtige Reihenfolge bringen: \begin{align*} S & \step{} ABCS \ | \ \epsilon \\ BA & \step{} AB \\ CA & \step{} AC \\ CB & \step{} BC \\ A & \step{} a \\ B & \step{} b \\ C & \step{} c \end{align*} Offensichtlich kann jedes Wort in $L$ erzeugt werden, allerdings auch Wörter wie $abcabc$, die nicht in $L$ sind. Können wir die erzeugte Sprache beschreiben? Ich glaube, es ist die Sprache aller $abc$-Wörter $w$ mit gilt \begin{align*} & \#_a(w) \geq \#_b(w) \geq \#_c(w) \quad \textnormal{und} \\ & \#_a(v) \geq \#_b(v) \geq \#_c(v) \quad \textnormal{für alle Präfixe $v$ von $w$} \end{align*} wobei $\#_b(v)$ die Anzahl der in $v$ enthaltenen $b$ ist.

Nachdem also unser erster Versuch gescheitert ist, unternehmen wir einen zweiten. Wir stellen uns die Ableitung als aus zwei Phasen bestehend vor. In der ersten wird eine Wortform $w \in \{A,B,C\}$ erzeugt mit \begin{align*} \#_A(w) = \#_B(w) = \#_C(w) \end{align*} erzeugt. In einer zweiten wandert ein Kontrollsymbol von links nach rechts durch und wandelt jeden Großbuchstaben in einen Kleinbuchstaben um, weigert sich aber bei Großbuchstaben, die in der falschen Reihenfolge stehen. Wir brauchen nun sieben Nichtterminale $N = \{S,A,B,C,X,Y,Z\}$. Für $S$ haben wir die Produktionen \begin{align*} S & \step{1} SABC \\ S & \step{2} X \end{align*} so dass $S \Step{}^* X (ABC)^n$ gilt. Als nächstes brauchen wir die Vertauschregeln, um alles in die richtige Reihenfolge zu bringen: \begin{align*} BA & \step{3} AB \\ CA & \step{4} AC \\ CB & \step{5} BC \end{align*} Die Nichtterminale $X,Y,Z$ stehen für folgendes:

$X$: will $A$ in $a$ umwandeln: \begin{align*} XA & \step{6} aX \end{align*} Zu jedem Zeitpunkt können wir beschließen, nun keine $A$ in $a$ mehr umzuwandeln, sondern nun $B$-Symbole zu erwarten: \begin{align*} X & \step{7} Y \end{align*}
$Y$: will $B$ in $b$ umwandeln oder mit $C$ fortfahren: \begin{align*} YB & \step{8} bY \\ Y & \step{9} Z \end{align*}
$Z$: will $C$ in $c$ umwandeln. Wir können aber auch einfach aufhören, zum Beispiel wenn wir den rechten Rand erreicht haben: \begin{align*} ZC & \step{10} cZ \\ Z & \step{11} \epsilon \end{align*}

Nun müssen wir zeigen, dass die Grammatik die Sprache $L$ erzeugt. Für jedes Wort $a^n b^n c^n \in L $ müssen wir zeigen, dass wir es ableiten können: \begin{align*} & S \Step{1}^* S(ABC)^n \Step{2} X(ABC)^n \Step{3,4,5}^* X A^n B^n C^n\\ & \Step{6}^* a^n X B^n C^n \Step{7} a^n Y B^n C^n \Step{8}^* a^n b^n Y C^n \Step{9} a^n b^n Z C^n \Step{10}^* a^n b^n c^n Z \Step{11}^* a^n b^n c^n \end{align*}

Als zweites müssen wir zeigen, dass jedes abgeleitete Wort $S \Step{}^* w \in \{a,b,c\}^*$ auch in $L$ ist, also die Form $a^n b^n c^n$ haben. Wir machen das nur zu 80% formal.

Die erste Beobachtung ist: solange $S$ in der Wortform $\beta$ vorkommt, hat diese die Form $\beta = S \gamma$ mit $\gamma \in \{A,B,C\}^*$ enthält gleich viele $A$ wie $B$ wie $C$.

Behauptung Sei $\#_{A,a}(\beta)$ die Anahl der $A$ und $a$ in der Wortform $\beta$. Wenn $S \Step{} \beta$, dann gilt

$\#_{A,a}(\beta) = \#_{B,b}(\beta) = \#_{C,c}(\beta)$
Außer $A,a,B,b,C,c$ enthält $\beta$ höchstens ein weiteres Symbol, und dies ist in $\{S,X,Y,Z\}$.
Wenn $\beta$ das Symbol $X$ enthält, dann ist $\beta = a^* X \gamma $. Wenn es $Y$ enthält, dann ist $\beta = a^* b^* Y \gamma $. Wenn es $Z$ enthält, dann ist es $\beta = a^* b^* c^* Z \gamma$. In allen drei Fällen enthält $\gamma$ keine Terminalsymbole.
Wenn es kein Symbol in $S,X,Y,Z$ enthält, dann ist es von der Form $\beta = a^* b^* c^* \gamma$ und $\gamma$ enthält keine Terminalsymbole.

Wir behaupten also, dass das $\gamma$ in Punkt 3 aus den Nichtterminalen $A,B,C$ besteht, die jedoch nicht in der korrekten Reihenfolge sein müssen. Wir können auch gar nicht verbieten, dass in einer Ableitung die Vertausch-Regeln 3,4,5 und die Kontroll-Regeln 6,7,8,9,10,11 vermischt angewandt werden.

Die Behauptung kann man beispielsweise mit Induktion über die Länge der Ableitung zeigen. Intuitiv gesprochen: Sie gilt unmittelbar, nachdem $S \rightarrow X$ angewandt wurde; danach überträgt sich ihre Gültigkeit Schritt für Schritt (z.B. weil Terminalsymbol immer nur links vom Symbol $X / Y / Z$ erzeugt werden können).

Wenn nun also $S \rightarrow a^* b^* c^* \gamma$ und $\gamma$ kein Nichtterminal $S,X,Y,Z$ enthält, also $\gamma \in \{A,B,C\}^*$, dann können keine weiteren Produktionen angewandt werden und die Ableitung endet. Wenn das also ein Wort sein soll, muss $\gamma = \epsilon$ gelten und somit $\beta = a^* b^* c^*$ gelten. Da nach Behauptung die Anzahl der drei Symbole gleich sein muss, gilt also $\beta = a^n b^n c^n$ und somit $\beta \in L$.

Beispiel Im Teilkapitel 5.10 gab es Übungsaufgabe 5.10.2, in der zu zeigen war, dass \begin{align*} L = \{ 1^n \ | \ n = 2^d \textnormal{ für ein $d \in \N$ }\} \end{align*} nicht kontextfrei ist. Allerdings ist $L$ kein sehr kompliziertes Gebilde. So könnten Sie recht einfach ein Programm schreiben, dass für ein Eingabewort prüft, ob es in $L$ ist. Können wir also auch eine formale Grammatik schreiben?

Dies geht sogar nohc einfacher als die obigen Sprachen. Wir schaffen eine Startregel: \begin{align*} S & \step{1} L1R \end{align*} Die Nichtterminale $L$ und $R$ zeigen den linken und rechten Rand an. Wir können am linken Rand einen "Verdopplungssymbol" $D$ erzeugen. Dies kann nur nach rechts durchwandern und bei $R$ verschwinden und verdoppelt dabei jede $1$, die es trifft: \begin{align*} L & \step{2} LD \\ D1 & \step{3} 11D \\ DR & \step{4} R \end{align*} Schlussendlich definieren wir End-Produktionen, die die Randmarkierungen löschen: \begin{align*} L & \step{5} \epsilon \\ R & \step{6} \epsilon \end{align*} Hier sehen Sie nun ein Beispiel für eine Ableitung: \begin{align*} S \Step{1} L1R \Step{2} LD1R \Step{3} L11DR \Step{2} LD11DR \Step{3} L11D1DR \Step{4} L11D1R \Step{3} L1111R \Step{5} 1111R \Step{6} 1111 \end{align*}

Wagen wir ein letztes Beispiel: die Sprache aller Wörter, deren Länge eine Quadratzahl ist. Spätestens dieses Beispiel sollte Sie davon überzeugen, dass allgemeine formale Gramatiken, im Gegensatz zu kontextfreien und regulären, nicht nur Formate syntaktisch beschreiben, sondern komplizierte Rechnungen durchführen können. Sie stellen somit ein völlig andersartiges Biest dar.

Beispiel Sei $L$ die Sprache aller Wörter über $\Sigma = \{1\}$, deren Länge eine Quadratzahl ist. Wir werden als erstes eine Multiplikationsgrammatik erzeugen. Dies soll eine Menge von Produktionen sein, die Ableitungen der Form \begin{align*} L A^m B^n R \Step{} L \tilde{A}^m B^n C^{mn} R \end{align*} ermöglicht. Wenn wir dies geschafft haben, sind wir fertig. Mittels \begin{align*} S & \rightarrow L S' R \\ S' & \rightarrow A S' B \ | \ \epsilon \end{align*} können wir alle $S \Step{}^* L A^m B^m R$ ableiten. Die Multiplikationsgrammatik wandelt uns dies in $L A^m B^m C^{m^2} T$ um. Schlussendlich führen wir ein Killersymbol $K$ ein, das bei $T$ entsteht und sich nach links durcharbeitet, dabei die $C$ in $1)\ umwandelt und die \(\tilde{A},B$ durch $\epsilon$ ersetzt: \begin{align*} R & \rightarrow K \\ CK & \rightarrow K1 \\ BK & \rightarrow K \\ \tilde{A}K & \rightarrow K \\ LK & \rightarrow \epsilon \end{align*} Es bleibt also, die Multiplikationsgrammatik zu entwerfen, die, um es zu wiederholen, \begin{align*} L A^m B^n R \Step{} L \tilde{A}^m B^n C^{mn} R \end{align*} ermöglicht, aber nicht wirklich viel mehr. Wir erschaffen die Produktion \begin{align*} A & \rightarrow \tilde{A} X \end{align*} Das neue Nichtterminal $\tilde{A}$ bedeutet soviel wie "ein $A$, das bereits abgearbeitet worden ist." Das Nichtterminal $X$ bedeutet: erzeuge rechts vom $B$-Block einen $C$-Block gleicher Länge. Wir wollen also \begin{align*} L \tilde{A}^i X A^j B^n R \Step{} L \tilde{A}^i A^j B^n C^n R \end{align*} Die einfachste Möglichkeit ist vielleicht, das $X$ nach rechts durchrutschen zu lassen und dabei jedes $B$ durch ein $B \tilde{C}$ ersetzen zu lassen: \begin{align*} XA & \rightarrow AX \\ XB & \rightarrow B \tilde{C}X\\ XR & \rightarrow R\\ X\tilde{C} & \rightarrow \tilde{C}X \end{align*} Das $X$ erzeugt also von seinem Entstehen bis zu seinem Verschwinden bei $R$ genau $n$ viele $\tilde{C}$-Symbole. Wir erstellen nun Regeln, die uns zwingen, jedes $\tilde{C}$ nach rechts laufen zu lassen, wo sie in ein $C$ umgewandelt werden können: \begin{align*} \tilde{C} B & \rightarrow B \tilde{C} \\ \tilde{C} C & \rightarrow C \tilde{C} \\ \tilde{C} R & \rightarrow R \end{align*} Überzeugen wir uns, dass dies den gewünschten Effekt hat.

Wir können $R$ nur loswerden, indem wir es in das Killersymbol $K$ umwandeln. Das Killersymbol kann nur bei $L$ verschwinden. Dazwischen kann es nur die Zeichen $\tilde{A}, B, C$ passieren. Zum Zeitpunkt, wo wir $R \rightarrow K$ anwenden, darf die Wortform also keine $A$-Symbole mehr enthalten.
Wir können eine $A$ nur verschwinden lassen durch $A \rightarrow \tilde{A} X$ und $X$ nur auf diese Weise entstehen lassen. Wir produzieren also, wenn wir mit $L A^m B^n R$ beginnen, im Laufe der Ableitung genau $m$ mal ein $X$.
Um ein $X$ wieder verschwinden zu lassen, muss es den ganzen $B$-Block durchlaufen und produziert damit insgesamt $n$ viele (\tilde{C}\).
Da wir insgesamt $m$ viele $X$ produzieren und jedes $X$ insgesamt $n$ viele $\tilde{C}$ produziert, werden insgesamt $mn$ viele $\tilde{C}$ erzeugt.
Jedes $\tilde{C}$ kann nur in ein $C$ umgewandelt werden. Es entstehen also insgesamt $mn$ viele $C$.

Wenn wir also aus $L A^m B^n R$ ein Wort ableiten, so muss zum Zeitpunkt der Produktion $R \rightarrow K$ die Wortform so aussehen: \begin{align*} \tilde{A}^m B^n C^{mn} R \Step{} \tilde{A}^m B^n C^{mn} K \end{align*} Wir können die Produktion $R \step{} K$ zwar schon früher anwenden; wenn da allerdings noch $A$- oder $\tilde{C}$-Symbole enthalten sind, ist es game over: wir könnten die nie mehr in Terminale umwandeln.

In einer leichten Variation können wir auch die Sprache \begin{align*} \{a^m b^n c^{mn} \ | \ m,n \geq 0 \} \end{align*} erzeugen.

Die Sprache \{a^m b^n c^{m+n}\} können wir eh: die ist sogar kontextfrei. Wir können also Arithmetik mit formalen Grammatiken "programmieren".

Übungsaufgabe Geben Sie ein formale Grammatik für \begin{align*} L = \{w\texttt{:}w \ | \ w \in \{a,b\}^* \} \end{align*} an. Dies ist auch ein Paradebeispiel für eine Sprache, die nicht kontextfrei ist.

Überlegen Sie, wie man "lineare Suche" implementieren könnte:

Übungsaufgabe Sei $L$ die Sprache über $\Sigma = \{a,b,:,;\}$ mit \begin{align*} L := w:w_1;w_2; \dots; w_n \end{align*} mit $w, w_1, \dots, w_n \in \{a,b\}^*$. Sie implementiert also im Prinzip die Funktion

List.member x list

die überprüft, ob $x$ in der angegebenen Liste enthalten ist: \begin{align*} abba\text{:}aaaaaaa\text{;}abbbb\text{;}abba\text{;}bbbb \in L \\ abba\text{:}aaaaaaa\text{;}abbbb\text{;}abbba\text{;}bbbb \not \in L \\ \end{align*} Tip: das ist einfach, wenn Sie bereits eine Grammatik für das vorherige Problem haben. Erzeugen Sie $wXwY$ und lassen dann aus $X$ und $Y$ den Rest der Liste entstehen.

Sie haben sicherlich gemerkt, dass wir die Grammatikproduktionen nun nicht mehr nur zum Erzeugen verwenden wie bei kontextfreien Sprachen, sondern zum Umformen, Rumschieben, Kopieren etc. Es ist nun an der Zeit, die Welt der Grammatiken zu verlassen und zu formalisieren, was man mit Umformen, Rumschieben, Kopieren erreichen kann. In anderen Worten: eine Formalisierung des Begriffs des Berechnens.