Greibach-Normalform (GNF)

Die Greibach-Normalform 

Eine Grammatik auf Greibach-Normalform enthält in ihrer Regelmenge nur Produktionen, die genau eine Nichtterminalvariable auf der linken Seite stehen haben, und auf der rechten Seite können ausschließlich ein Terminalsymbol als erstes und danach beliebig viele Nonterminalsymbole stehen.

In der Regelmenge der Grammatik auf Greibach-Normalform darf das logische ”oder” jedoch immernoch vorkommen. Somit lässt sich ein Nonterminalsymbol auf mehrere “Möglichkeiten” ableiten, bspw:

S –> a|bA|qCD

Jede rechtslineare Grammatik befindet sich auf GNF, wenn die Grammatik wohlgemerkt l-frei sei (l = das leere Wort).