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}undP′′ = {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.
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.
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?
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 ..." ;-)
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos