Sind die beiden Grammatiken G und G′′ äquivalent?

Question

Betrachten Sie die Grammatik G = (Σ, N, S, P) mit Σ = {a, b, c}, N = {S, B, C, X} und

P = {S → aSa ∣ aXa,
X → BCX ∣ BC,
CB → BC,
Ca → ca,
Cc → cc,
Bc → bc,
Bb → bb}.

Betrachten Sie jetzt die Grammatik G′′ = (Σ, N, S, P′′) mit Σ = {a, b, c}, N = {S, A, B, C, X}
und
P′′ = {S → aSa ∣ aXa,
X → BC,
B → bB ∣ b,
C → cC ∣ cA,
A → a, }.

Sind die beiden Grammatiken G und G′′ äquivalent? Begründen Sie Ihre Antwort.

Answer 1

Sind die beiden Grammatiken G und G′′ äquivalent? Begründen Sie Ihre Antwort.

Die beiden Grammatiken sind gleich, wenn sie dieselben Sprachen \(\mathcal{L}(G)=L=L''=\mathcal{L}(G'')\) erzeugen. Dies kannst Du auf verschiedene Arten nachweisen (z. B. durch einen Ableitungsbaum). Sind sie nicht gleich, musst Du ein Gegenbeispiel angeben, das in \(L\), aber nicht in \(L''\) liegt.

Comments

Ableiteung der ersten Sprache:

S => aXa => aBCXa => aBCBCa => aBBCCa =>aBBCca => aBBcca =>aBbcca => abbcca

Ableitung der zweiten Sprache:

S => aXa => aBCXa => aBCBCa => aBBCCa =>aBBCca => aBBcca =>aBbcca => abbcca

Bei der ersten und zweiten Sprache bei einer Ableitung bekommt man das gleiche Wort , somit sind die äqiuvalent. Kann man das so beweisen?

---

Bei der ersten und zweiten Sprache bei einer Ableitung bekommt man das gleiche Wort , somit sind die äqiuvalent. Kann man das so beweisen?

Leider nicht. Das riecht nicht als Beweis aus, da Du nur ein einziges Wort geprüft hast. Du musst theoretisch alle Wörter prüfen, um einen mathematisch stichhaltigen Beweis zu liefern. Dass das funktioniert ist aber ein guter Indikator! In der Aufgabenstellung heißt es zum Glück "Begründen Sie ..." und nicht "Beweisen Sie ..." ;-)