d): N --> Lamda bei Greibach-Normalform?

Question

Aufgabenteil Teil d: Wieso ist eine rechtslineare Grammatik automatisch in Greibach-Normalform, wenn bei einer rechtslinearen Grammatik eine Produktion der Form N --> Lamda möglich ist, was bei einer Grammatik in Greibach-Normalform nicht erlaubt ist?

Wenn ich eine rexchtslineare Grammatik mit Abbildungen auf Lamda habe, liegt sie doch nicht in GNF vor, oder sehe ich das falsch?

Answer 1

Du siehst das richtig. In den Folien wird explizit von einer rechtslinearen Grammatik geredet, die Lambda-frei ist. Und ebenfalls ist gilt: PRL ⊆ PGREI ∪ {λ}. Auch hier wird das Lambda wieder extra behandelt. 

In der Frage hätte man wohl besser von einer Lambda-freien rechtslinearen Grammatik sprechen müssen.

Grüße

Simon

 

Answer 2

Sie haben recht, dass die Regel N --> lambda natürlich bei der Greibach Normalform nicht erlaubt ist.

Die Lösung in der Klausur ist das minimal geforderte (und streng genommen auch nicht ganz korrekt), wenn Sie an dieser Stelle geschrieben hätten, dass n--> zu viel ist, dann hätten Sie natürlich auch die volle Punktzahl erhalten.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König