Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Kann man mit w nicht auch aabbcccbbccc produzieren?

–1 Punkt
29 Aufrufe
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.
Gefragt 25, Sep 2015 in 2013-H-02 von uafjv uafjv Tutor(in) (167,840 Punkte)  

2 Antworten

0 Punkte

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)

 

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,840 Punkte)  
0 Punkte

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?

Beantwortet 25, Sep 2015 von uafjv uafjv Tutor(in) (167,840 Punkte)  
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)
...