Schritt (4) Umbenennung doppelt

Question

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?

Answer 1

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

Comments

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.