Verständnis Greibach-Normalform HK 15 3d)

Question

Hallo,

im Tutorium heißt es, man braucht eine Lamdafreie rechtslineare Grammatik nicht umformen, um in die GNF zu gelangen. Daraus leite ich ab, dass in der GNF kein Lamda enthalten müsste, was hier aber der Fall ist , da S' -> lamda...  Ich verstehe das nicht so ganz. Danke!

Answer 1

Eine $\lambda$-freie Grammatik ist so definiert, dass die Regel $S \rightarrow \lambda$ erlaubt ist, wenn $S$ auf keiner rechten Seite einer Regel vorkommt. Sonst sind aber keine $\lambda$-Regeln erlaubt.