kann ich Schritt "(1) G lambda-frei machen" nicht IMMER ohne neuen Startzustand S' machen?

Question

Hallo,

kann ich Schritt "(1) G lambda-frei machen" nicht IMMER ohne neuen Startzustand S' machen?

In einem Beispiel in den Folien (Kap. 3, Seite 32) gibt es in P nur eine Startzeile, diese hat lambda am Ende und S kommt auch rechts vor: ([ und ] sind Terminale)
P = { S --> SS | [S] | lambda }

Nach Schritt (1) hat man:
P = { S --> SS | [S] | S | [ ] }
Also lambda wurde entfernt, der Rest beibehalten und alles ergänzt, was eintreten kann, wenn S --> lambda. Im neuen P kann S also nie nach lambda gehen, was ja aber laut der Methodik mit Einführung von S' gehen muss.

Bei Aufgabe 59 (KON-AG) vom Aufgabenpool steht lambda NUR in EINER Zeile (... B --> ... | ... | lambda), also nicht in der Startzeile mit S und das B, was eben lambda werden kann, steht auch auf weiteren rechten Seiten. Hier wird für Schritt (1) lambda entfernt, alle Zeilen ansonsten beibehalten und alles in allen Zeilen ergänzt, was eintreten kann, wenn S --> lambda - also wie oben beschrieben.

Für mich sind die beiden Beispiele das gleiche Schema und ich erkenne nicht, wieso es notwendig ist, dass man überhaupt einen neuen Startzustand S' einführen soll.
Bei der Nachklausur 2013 (Aufgabe 3 a) hat man lambda nur in der Startzeile bei S und S auch nur auf einer rechten Seite (in der Startzeile). Hier wird S' --> S | lambda eingeführt und dann wohl nix mehr geändert (bis auf lambda danach weg) und S immer stehen gelassen. Wenn ich es hier machen würde wie oben beschrieben, müsste man für Schritt (1) ja neben S --> ASB auch noch S --> AB haben (hier wurden leider keine Zwischenschritte angegeben).

Ich hoffe, mir kann jemand weiterhelfen.

Und wenn man S' ergänzt.

 

Answer 1

Hallo,

diese beiden Produktionsmengen sind nicht äquivalent:

{ S --> SS | [S] | lambda }

bzw.

{ S --> SS | [S] | S | [ ] }

Mit der unteren Menge kann das leere Wort nicht erzeugt werden, oben schon. Damit man auch unten das leere erzeugen kann, könnte man bspw. ein neues Startsymbol S' einführen, zusammen mit der Regel S' --> S | lambda. Auf diese Weise erhält man nach Anwendung des ganzen Algorithmus eine Grammatik, die in CNF ist und trotzdem das leere Wort erzeugen kann (im CYK-Algorithmus muss man die lambda-Regel dann separat betrachten.

Viele Grüße

Lukas König

Nachtrag:

Sie haben allerdings Recht damit, dass bei der Nachklausur 2013 die Regel S --> AB fehlt. Ich habe das korrigiert.

Viele Grüße

Lukas König