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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
49 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.
in 2013-H-02 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte

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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 Pluspunkte 0 Minuspunkte

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?

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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!
0 0
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.
0 0
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)
...