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

1 Pluspunkt 0 Minuspunkte
48 Aufrufe
In der Aufgabe wird ABC zu AG ; G-->BC ; G wird dabei sowohl in der Ableitung bei S, als auch bei B genutzt. Wäre es in der Klausur erlaubt auch zwei Produktionen einzuführen die letzendlich zum gleichen Ergebnis führen, also nicht final vereinfacht? Im Buch steht (S.233), dass das Zusammenfassen gefährlich werden kann. Für welche Fälle kann das Zusammenfasssen zu Problemen führen?
in KON-AD von Niklas Hasebrook Tutor(in) (101k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
 
Beste Antwort

Ja, das wäre absolut auch in Ordnung!

Wenn man so einfach sagen könnte, wann das Zusammenfassen zu Problemen führen kann, würde es wahrscheinlich gar nicht mehr zu Problemen führen smiley Solange man einen einfachen übersichtlichen Fall wie hier hat, ist es kein Problem, die Variable doppelt zu benutzen, denn man "sieht" ja, dass keine Nebeneffekte entstehen können (also Ableitungen, die man nicht haben wollte). Wird es aber komplexer, kann man leicht die Übersicht verlieren, denn die Ableitung durch Grammatiken ist ja hochgradig nichtdeterministisch. Auch bei der Implementierung eines Algorithmus für die CNF würde man normalerweise die sichere Variante wählen, denn zu entscheiden, wann eine Variable mehrfach genutzt werden kann, ist knifflig. (Wahrscheinlich gibt es dafür schon auch Regeln, die man einsehen würde, aber wir behandeln das in der Vorlesung nicht, und daher gilt einfach: Wenn Sie sich zutrauen, den Überblick zu behalten, dann komprimieren Sie die Grammatik, so weit Sie wollen, und wenn nicht, dann bleiben Sie auf der sicheren Seite.)

von Dozent (10.1m Punkte)  
ausgewählt von Niklas Hasebrook
0 0
PS. Also alle Fälle vom Typ wie in dieser Aufgabe sind natürlich immer in Ordnung. Wenn genau dieselbe Folge $ABC$ zweimal auftaucht, dann kann man sie logischerweise auch immer auf dieselbe Weise und mit denselben Variablen behandeln.
...