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!
 

 

Schritt (4) Umbenennung doppelt

+1 Punkt
32 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?
Gefragt 24, Jan 2017 in KON-AD von Niklas Hasebrook Tutor(in) (100,850 Punkte)  

Eine Antwort

+1 Punkt
 
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.)

Beantwortet 24, Jan 2017 von Lukas König Dozent (10,065,090 Punkte)  
ausgewählt 24, Jan 2017 von Niklas Hasebrook
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.
...