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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
196 Aufrufe
Hallo,

in der Musterlösung wird angegeben, dass S->aC und S->ac hinzufügen und S->aBC löschen reichen würde um auf die geforderte Grammatik zu kommen. Angenommen man leitet S nun zu allererst nach der erstgenannten Regel ab (also S->aC), dann fehlt anschließend doch jegliche Regel um weitere Umformungen vornehmen zu können oder?

Weder eine Regel mit aC noch eine Regel mit nur C auf der linken Seite ist in der neuen Grammatik enthalten. Verstehe ich das falsch, oder ist das ein Fehler?
in 2017-H-03 von uoioh uoioh Lernwillige(r) (340 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo,

wenn man mit der Grammatik das Wort ac ableiten will, macht man das gleich über die Regel S->ac. Wenn man längere Wörter ableiten will, verwendet man zuerst die Regel  S->aSBC. Diese ist noch in der veränderten Grammatik enthalten. Um das Wort nun zu beenden kann zum Schluss noch S->ac abgeleitet werden. Vor dem a stehen in dem Fall aber noch weitere as und dahinter die abgeleitet BCs. Man hat also z.B. aaacBCBC. Und um dieses Wort in die richtige Reihnenfolge zu bringen kann man dann die restlichen Regeln anwenden.

Ich hoffe das beantwortet deine Frage, sonst frag gern nochmal nach.

Viele Grüße,

Verena (Tutorin)
von upfgy upfgy Eins-Komma-Null-Anwärter(in) (1.8k Punkte)  
0 0
Vielen Dank für die schnelle Antwort! Dadurch erschließt sich mir der Sinn dieser Produktionsregel. Allerdings hätte ich dann noch eine kurze Frage: Angenommen man würde jetzt doch, wie bereits erwähnt zu allererst die Regel S->aC verwenden, dann ist es doch nicht möglich weiter abzuleiten und wir "enden" mit einem Nonterminalsymbol in unserem abgeleiteten Wort. Ist das überhaupt zulässig? Ich meine irgendwo gelesen zu haben, dass die Produktionsregeln so formuliert werden müssen, dass letztendlich kein Nonterminalsymbol mehr vorhanden ist. Oder liege ich da falsch?
0 0
Man verwendet diese Regel nur wenn man ein längeres Wort ableiten will. Ansonsten könnte man es, wie du gesagt hast, nicht weiter ableiten. Um das Wort zu beenden muss immer als letztes die Regel S->ac angewendet werden, sonst kann man es nicht vollständig ableiten.
...