0 Daumen
51 Aufrufe

Hallo,

ich verstehe nicht ganz wie ich bei einer gegebenen Grammatik ablesen kann, welche Sprache akzeptiert wird.


Ein Beispiel aus der Vorlesung ist wie folgt:

G=(Σ, V, R, S) mit Σ={a,b,c}, V={S, B, C} und R={S ↦ aSBC, S ↦ aBC, CB ↦ BC, aB ↦ ab, bB ↦ bb, bC ↦ bc, cC ↦ cc}

Die von G akzeptierte Sprache ist L(G)= {a^n b^n c^n l n ≥ 1}.

Wie sehe ich das ?

Gefragt von

1 Antwort

+3 Daumen

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).

Beantwortet von 8,3 k

Danke für deine Antwort!

Oh je, ich probiere da einfach irgendwie rum ? Hab eher gehofft, dass es einen "schönen" Weg gibt das zu lösen.

Also wäre ich bei diesem Beispiel früher oder später (auf jeden Fall) auf die Form a^n b^n c^n gekommen?


Ich dachte eigentlich, dass mir das Beispiel meine eigentliche Aufgabe etwas verständlicher macht. Jetzt stehe aber vor folgender Grammatik:

Σ = {a,b}, V={S, A, B}, R={S ↦ aB (1) , S ↦ bA (2), A ↦ a (3), A ↦ aS (4), A ↦ bAA (5), B ↦ b (6), B ↦ bS (7), B ↦ aBB (8) }

Ich hab also versucht da abzuleiten, Regeln mehrfach angewandt, aber immer andere Wörter rausbekommen und kein Muster festgestellt.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...