text: Kann man mit w nicht auch aabbcccbbccc produzieren? - Theoretische und technische Informatik - ganz praktisch
  Kann man mit w nicht auch aabbcccbbccc produzieren?
  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.
  Gefragt 25, Sep 2015 in 2013-H-02 von uafjv uafjv Tutor(in) (168k Punkte)
  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.
  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?
  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.
  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.