Rechtslineare Grammatik in Greibach-NF

Question

Ist es in der Greibach-NF erlaubt, von einem beliebigen Non-Terminalsymbol auf das leere Wort abzuleiten? Weil so wie ich das auf 3-33 (Vorlesung) verstehe, ist das nicht möglich. Jedoch steht in der oben genannten Aufgabe in Aufgabenteil d), dass man nichts machen müsste, um von einer rechtslinearen Grammatik auf Greibach-NF zu kommen. Bei einer rechtslinearen Grammatik sind aber Produktionen von beliebigen Non-Terminalsysmbolen auf Lambda erlaubt.

Müsste man dann nicht solche Produktionen irgendwie sonderbehandelt, bzw. Lambda-frei machen?

Answer 1

Hallo ueyfv,

da hast du recht, die rechtslineare Grammatik muss lambdafrei sein, damit man 'nichts' machen muss. Ansonsten muss man sie lambdafrei machen.

Die einzige Sonderregel bei der Greibach-Normalform mit Lambda ist, dass das Startsymbol auf Lambda abgebildet werden darf, wenn es auf keiner rechten Seite auftaucht (und zwar genau dann, wenn das leere Wort zur Sprache gehört)

Viele Grüße

Anne (Tutorin)