Warum fügen wir einen neuen Startzustand S0 -> S hinzu, wenn wir eine Grammatik in Chomsky Normalform umwandeln wollen? Was läuft schief, wenn wir das nicht tun?Chomsky Normaler Formularkonvertierungsalgorithmus
Zuerst dachte ich, es ist wegen der Epsilon-Regeln. Wir entfernen jedoch keine epsilon-Regel aus der Startvariablen. Also, was ist der Vorteil des Hinzufügens von S0 -> S?
Danke
Je nachdem, ob die leere Zeichenfolge in der Sprache ist, haben Sie möglicherweise die Regel $ S -> \ epsilon $ (oder $ S_0 -> \ epsilon $). Dies könnte eine beliebige Anzahl von Symbolen $ S $ löschen, wenn diese auf der rechten Seite der Regeln erscheinen könnten. Da wir nicht möchten, dass das Startsymbol wieder erscheint, führen wir ein neues ein.
Auf diese Weise erhalten wir genau ein weiteres Symbol pro Anwendung einer Regel A -> BC.
Ich denke, ich habe eine Erklärung. Wenn eine Grammatik ist wie folgt:
S --> S1
S1 --> S
S1 --> a
Dann wird bei dem Schritt der Entfernung „-Einheit Regeln“, da wir eine bestimmte Reihenfolge nicht berücksichtigen, können wir S entfernen -> S1 zuerst und wir haben:
S1 --> S1
S1 --> a
und die Startvariable wird vollständig entfernt.
Ich glaube nicht, dass es ein Problem macht, denn selbst wenn Sie die Regel S ---> \ epsilon haben, werden Sie es nicht entfernen, da eine epsilon-Regel nur gelöscht wird, wenn ihre Variable nicht das Startsymbol ist. –
Der Punkt ist, dass Sie mit CNF wissen, dass die Ableitung eines Strings der Länge n hat n-1 Regeln A-> BC und n der Form A-> a. Die Grammatik S-> A, A-> AS, A-> a, S-> eps könnte den String a auf beliebig viele Arten ableiten. Dies ist nicht das, was Sie von einer ** normalen Form ** wünschen. –