Herzlich Willkommen in der Stacklounge! :-)
Wie sehe ich das ?
Du musst die gegebene Grammatik analysieren. Ich weiß, dass das leichter geschrieben als getan ist. Da es keinen wirklich guten Algorithmus gibt, der einen sicher zum Ziel führt, hilft meistens nur (wie auch bei Zahlenreihen) systematisches Ausprobieren.
Zu Beginn ist es sinnvoll, sich die Terminalsymbole zu notieren (hier \(a,b,c\)). Diese werden sehr wahrscheinlich in der durch \(G\) erzeugten Grammatik auftauchen (sonst wären die damit verbundenen Produktionsregeln redundant). An dieser Stelle sei angemerkt:
Die von G akzeptierte Sprache
Eine Grammatik akzeptiert eine Sprache nicht, sondern erzeugt sie.
Nun musst Du "systematisch Ausprobieren". D. h. Du leitest so viele Wörter ab, bis Du eine Struktur in den Wörtern erkennst, die Du dann formal notieren kannst. Wichtig ist dabei, dass die Wörter nicht wahllos zusammengewürfelt werden, sondern alle Ableitungsregeln der Grammatik (ggf. auch mehrere Male) verwendet werden.
Wir beginnen mit dem Startsymbol \(\mathrm{S}\) und wenden die erste Ableitungsregel mehrfach an:
\(S\mapsto \mathrm{aSBC}\)
\(S\mapsto \mathrm{aaSBCBC}\)
\(\mathrm{S}\mapsto \mathrm{aaaSBCBCBC}\)
Man sieht, dass mit jedem Schritt ein \(a\) am Anfang hinzukommt. Nun wenden wir die zweite Produktionsregel auf jeden Zwischenschritt an:
\(\mathrm{S}\mapsto \mathrm{aaBCBC}\)
\(\mathrm{S}\mapsto \mathrm{aaaBCBCBC}\)
\(\mathrm{S}\mapsto\mathrm{ aaaaBCBCBCBC}\)
Man erkennt, dass von jeder Sorte an Terminal- (\(\mathrm{a}\)) und Nichtterminal-Symbolen (\(\mathrm{B},\mathrm{C}\)) gleich viel vorhanden ist. Mit der dritten Produktionsregel werden die Nichtterminalsymbole \(\mathrm{B}\) und \(\mathrm{C}\) "sortiert".
\(S\mapsto \mathrm{aaaaBBCBCBCC}\) \(\Longrightarrow\) \(S\mapsto \mathrm{aaaaBBBCBCCC}\) \(\Longrightarrow\) \(S\mapsto \mathrm{aaaaBBBBCCCC}\)
Du wirst gemäß den Produktionsregeln der Grammatik quasi gezwungen, diese Sortierung solange vorzunehmen, bis die obige Form erreicht ist, da es keine weitere Produktionsregel bestehend aus zwei Nichtterminal-Symbolen auf der linken Seite gibt, die von \(\mathrm{CB}\) abweicht. Du könntest jedoch auch zuerst mit der Produktionsregel \(\mathrm{aB}\mapsto \mathrm{ab}\) arbeiten, kämst dann aber früher oder später in die Notwendigkeit zu sortieren. Nun leitest Du mit den restlichen Produktionsregeln solange ab, bis Du nur noch Nichtterminal-Symbole (die Wörter der durch \(G\) erzeugten Sprache) hast. Wir erhalten für unser Beispiel das Wort:
\(\mathrm{aaaabbbbcccc}\) bzw. \(\mathrm{a}^4\mathrm{b}^4\mathrm{c}^4\)
Durch unsere Schritt-für-Schritt-Analyse haben wir gesehen, wie ein Wort in \(L(G)\) systematisch aufgebaut wird. Und diese Systematik hilft uns weitere Wörter relativ leicht zu antizipieren. Hätten wir nämlich die erste Produktionsregel \(5,6,7,...,n\) mal angewendet, hätten wir die Wörter
\(\mathrm{a}^5\mathrm{b}^5\mathrm{c}^5,\mathrm{a}^6\mathrm{b}^6\mathrm{c}^6,\mathrm{a}^7\mathrm{b}^7\mathrm{c}^7,...,\mathrm{a}^n\mathrm{b}^n\mathrm{c}^n\)
erhalten. Die Sprache \(L(G)\) ist also gegeben durch
\(L(G):=\left\{a^nb^nc^n\mid n\geq 1\right\}\)
Warum \(n\geq 1\)? Nun, das leere Wort \(\epsilon\) kann mit den gegebenen Produktionsregeln nicht abgeleitet werden. Die Angabe \(n\geq 1\) ist also nicht optional, sondern verpflichtend!
(Optionale) Übungsaufgabe von mir ;-)
Kannst Du Deine Grammatik so modifizieren, dass \(L(G)=\left\{a^nb^nc^n\mid n\in\mathbb{N}_0\right\}\)?
Wie auch beim Reverse Engineering, kann es sinnvoll sein, sich die Grammatik mit graphischen Hilfsmitteln zu veranschaulichen (z. B. durch Zeichnen eines Ableitungsbaums-/Syntaxbaums).
