Kann man mit w nicht auch aabbcccbbccc produzieren?

Question

Hallo,

lässt die in der Lösung gewählte Formulierung \( w=a^n b^{2n} c^{3n}\) auch Wörter zu, bei denen die Reihenfolge der Terminale nicht abc ist? Beispielsweise das Wort aabbcccbbccc lässt sich mit der gegebenen Grammatik produzieren.

Answer 1

Hallo,

Nein die Lösung lässt nur Wörter zu bei denen die Reihenfolge der Terminale abc ist, da dies die einzigen Wörter sind, die die gegebene Grammatik erzeugen kann. Bei dem von Ihnen gewählten Beispiel wären die b's die sich noch zwischen den c's befinden nach einer Regel umgewandelt worden, die es in der Grammatik nicht gibt. Es können nur C's umgewandelt werden vor denen ein b kommt und C's vor denen wieder ein c kommt aber keine C's vor denen ein b steht! Falls es zur Reihenfolge CB kommt, so muss das B erst durch die 2. Regel nach vorn gezogen werden.

Ich hoffe das hilft Ihnen weiter.

Viele Grüße,

Janina (Tutorin)

 

Answer 2

Mein Gedankengang war folgender:

S-->aSBBCCC-->aabbCCCBBCCC-->aabbcCCBBCCC... im dritten Schritt habe ich gemäß der Regel bC-->bc ein kleines c abgeleitet. Dieses kann doch nun nichtmehr die Position mit den vorangehenden b's tauschen oder? Wo leigt mein Denkfehler?

Comments

Hey,

wie du selbst gemerkt hast, kommst du damit nicht zu dem Wort. Du könntest deshalb an der Stelle erst mal mit einer anderen Regel weitermachen, welche dir erlaubt B und C zu tauschen. Die Umwandlug in Terminale kann ja noch später erfolgen!

---

Das Problem ist ja nicht, dass es hier keine Alternative gibt, sondern dass ich gemäß den Ableitungsregeln mit dieser Ableitung fortfahren kann und daraufhin das Wort aabbcccbbccc erhalte, welches nicht in der Sprache enthalten sein sollte. Natürlich kann ich durch CB-->BC auch korrekte Wörter ableiten, das ist mir schon klar.

---

Hallo,

eben da liegt das Problem: Sie kommen nach dieser Ableitung S-->aSBBCCC-->aabbCCCBBCCC-->aabbcCCBBCCC

nicht mehr auf ein Wort, was nur aus Terminalen besteht. Am besten versuchen Sie einmal die Ableitung so zu Ende zu führen.

Viele Grüße,

Janina(Tutorin)