S durch Produktionen ersetzen?

Question

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.

 

Answer 1

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