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!
 

 

S durch Produktionen ersetzen?

–1 Punkt
24 Aufrufe

Müsste man bei S`-->S|lambda  das S nicht durch dessen Produktionen ersetzen? Ist doch eine Umbennung.

Wenn nicht, warum wird in m=2 S' verwendet, sie hat hat doch nur indirekt die drüberstehende Produktionen.

 

Gefragt 22, Okt 2014 in KON-AD von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

0 Punkte
Hallo,

der Teil S'->S ist nicht in Chomsky-Normalform, wird aber benötigt, um zu gewährleisten, dass auch das leere Wort zur Sprache gehört.
Bezüglich des Cocke-Younger-Kasami-Algorithmus gilt, dass Sie diesen auch nur auf den Teil in Chomsky-Normalform (also ohne S'->S) anwenden. Demnach muss also im letzten Feld S auftauchen. Sie können aber S' auch, wie in der Musterlösung, mitschleppen.

Viele Grüße

Friederike Pfeiffer
Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...