0 Daumen
54 Aufrufe

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.

von

1 Antwort

+1 Punkt
 
Beste Antwort
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.

von 8,3 k

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...