7 Allgemeine Grammatiken (nicht im Sommersemester 2025)

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

Definition 7.2 (Ableitung und erzeugte Sprache). Sei $G$ eine formale Grammtik und ${\gamma }_1,{\gamma }_2\in (\mathrm{\Sigma }\cup N{)}^{\ast }$ zwei Wortformen. Wir schreiben ${\gamma }_1\stackrel{}{⟹}{\gamma }_2$, wenn wir $$\begin{array}{rl}{\gamma }_1& =u\alpha v\\ {\gamma }_2& =u\beta v\end{array}$$ schreiben können für Wortformen $u,v$, sodass $\alpha \to \beta$ eine Produktion von $G$ ist.

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

Nun schauen wir uns eine Beispielableitung an:

$$\begin{array}{r}S\stackrel{1}{⟹}ABCS\stackrel{1}{⟹}ABCABCS\stackrel{2}{⟹}ABCABC\stackrel{5}{⟹}ABACBC\stackrel{3}{⟹}AABCBC{\stackrel{8,8,9,9,10,10}{⟹}}^{\ast }aabcbc\end{array}$$

Beispiel 7.4 Versuchen wir nun, eine allgemeine formale Grammatik für die Sprache $$\begin{array}{r}L=\{a^n{b}^n{c}^n|n\ge 0\}\end{array}$$ 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{array}{rl}S& \stackrel{}{\to }ABCS|ϵ\\ BA& \stackrel{}{\to }AB\\ CA& \stackrel{}{\to }AC\\ CB& \stackrel{}{\to }BC\\ A& \stackrel{}{\to }a\\ B& \stackrel{}{\to }b\\ C& \stackrel{}{\to }c\end{array}$$ 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{array}{rl}& {\mathrm{\#}}_a(w)\ge {\mathrm{\#}}_b(w)\ge {\mathrm{\#}}_c(w)\text{und}\\ & {\mathrm{\#}}_a(v)\ge {\mathrm{\#}}_b(v)\ge {\mathrm{\#}}_c(v)\text{für alle Präfixe }v\text{ von }w\end{array}$$ wobei ${\mathrm{\#}}_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{array}{r}{\mathrm{\#}}_A(w)={\mathrm{\#}}_B(w)={\mathrm{\#}}_C(w)\end{array}$$ 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{array}{rl}S& \stackrel{1}{\to }SABC\\ S& \stackrel{2}{\to }X\end{array}$$ so dass $S{\stackrel{}{⟹}}^{\ast }X(ABC{)}^n$ gilt. Als nächstes brauchen wir die Vertauschregeln, um alles in die richtige Reihenfolge zu bringen: $$\begin{array}{rl}BA& \stackrel{3}{\to }AB\\ CA& \stackrel{4}{\to }AC\\ CB& \stackrel{5}{\to }BC\end{array}$$ Die Nichtterminale $X,Y,Z$ stehen für folgendes:

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

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{array}{rl}& S{\stackrel{1}{⟹}}^{\ast }S(ABC{)}^n\stackrel{2}{⟹}X(ABC{)}^n{\stackrel{3,4,5}{⟹}}^{\ast }X{A}^n{B}^n{C}^n\\ & {\stackrel{6}{⟹}}^{\ast }{a}^{n}X{B}^n{C}^n\stackrel{7}{⟹}{a}^{n}Y{B}^n{C}^n{\stackrel{8}{⟹}}^{\ast }{a}^n{b}^{n}Y{C}^n\stackrel{9}{⟹}{a}^n{b}^{n}Z{C}^n{\stackrel{10}{⟹}}^{\ast }{a}^n{b}^n{c}^{n}Z{\stackrel{11}{⟹}}^{\ast }{a}^n{b}^n{c}^n\end{array}$$

Als zweites müssen wir zeigen, dass jedes abgeleitete Wort $S{\stackrel{}{⟹}}^{\ast }w\in \{a,b,c{\}}^{\ast }$ 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{\}}^{\ast }$ enthält gleich viele $A$ wie $B$ wie $C$.

Wir behaupten also, dass das $$ in Punkt 3 aus den Nichtterminalen $$ 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 $$ angewandt wurde; danach überträgt sich ihre Gültigkeit Schritt für Schritt (z.B. weil Terminalsymbol immer nur links vom Symbol $$ erzeugt werden können).

Wenn nun also $$ und $$ kein Nichtterminal $$ enthält, also $$, dann können keine weiteren Produktionen angewandt werden und die Ableitung endet. Wenn das also ein Wort sein soll, muss $$ gelten und somit $$ gelten. Da nach Behauptung die Anzahl der drei Symbole gleich sein muss, gilt also $$ und somit $$.

Beispiel 7.6 Im Teilkapitel 5.10 gab es Übungsaufgabe 5.10.2, in der zu zeigen war, dass $$ nicht kontextfrei ist. Allerdings ist $$ kein sehr kompliziertes Gebilde. So könnten Sie recht einfach ein Programm schreiben, dass für ein Eingabewort prüft, ob es in $$ ist. Können wir also auch eine formale Grammatik schreiben?

Dies geht sogar nohc einfacher als die obigen Sprachen. Wir schaffen eine Startregel: $$ Die Nichtterminale $$ und $$ zeigen den linken und rechten Rand an. Wir können am linken Rand einen "Verdopplungssymbol" $$ erzeugen. Dies kann nur nach rechts durchwandern und bei $$ verschwinden und verdoppelt dabei jede $$, die es trifft: $$ Schlussendlich definieren wir End-Produktionen, die die Randmarkierungen löschen: $$ Hier sehen Sie nun ein Beispiel für eine Ableitung: $$

Beispiel 7.7 Sei $$ die Sprache aller Wörter über $$, deren Länge eine Quadratzahl ist. Wir werden als erstes eine Multiplikationsgrammatik erzeugen. Dies soll eine Menge von Produktionen sein, die Ableitungen der Form $$ ermöglicht. Wenn wir dies geschafft haben, sind wir fertig. Mittels $$ können wir alle $$ ableiten. Die Multiplikationsgrammatik wandelt uns dies in $$ um. Schlussendlich führen wir ein Killersymbol $$ ein, das bei $$ entsteht und sich nach links durcharbeitet, dabei die $$ in $$ durch $$ ersetzt: $$ Es bleibt also, die Multiplikationsgrammatik zu entwerfen, die, um es zu wiederholen, $$ ermöglicht, aber nicht wirklich viel mehr. Wir erschaffen die Produktion $$ Das neue Nichtterminal $$ bedeutet soviel wie "ein $$, das bereits abgearbeitet worden ist." Das Nichtterminal $$ bedeutet: erzeuge rechts vom $$-Block einen $$-Block gleicher Länge. Wir wollen also $$ Die einfachste Möglichkeit ist vielleicht, das $$ nach rechts durchrutschen zu lassen und dabei jedes $$ durch ein $$ ersetzen zu lassen: $$ Das $$ erzeugt also von seinem Entstehen bis zu seinem Verschwinden bei $$ genau $$ viele $$-Symbole. Wir erstellen nun Regeln, die uns zwingen, jedes $$ nach rechts laufen zu lassen, wo sie in ein $$ umgewandelt werden können: $$ Überzeugen wir uns, dass dies den gewünschten Effekt hat.

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

Wenn wir also aus $$ ein Wort ableiten, so muss zum Zeitpunkt der Produktion $$ die Wortform so aussehen: $$ Wir können die Produktion $$ zwar schon früher anwenden; wenn da allerdings noch $$- oder $$-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 $$ erzeugen.

List.member x list