Theoretische Informatik

Neben der Chomsky-Normalform gibt es für kontextfreie Grammatiken noch die Greibach-Normalform (nach S. Greibach).

Greibach-Normalform einer kontextfreien Grammatik

Definition:  Sei G = (V, T, P, S) eine kontextfreie Grammatik. G ist in Greibach-Normalform, wenn jede ihrer Produktionen die Form

X

au

mit X ∈ V, a ∈ T und u ∈ V* hat.

Zusätzlich ist die Produktion Sε als Ausnahme erlaubt, wobei dann das Startsymbol S nicht rekursiv sein darf.

Die rechte Seite jeder Produktion beginnt also stets mit einem Terminal­zeichen, danach kommen dann 0, 1, oder mehrere Variablen.

Die Greibach-Normalform ist somit eine Ver­allgemeinerung einer rechts­linearen Grammatik. Die Produktionen einer rechts­linearen Grammatik haben ebenfalls die Form Xau mit X ∈ V, a ∈ T, jedoch mit u ∈ V^?, d.h. bei einer rechts­linearen Produktion darf u höchstens aus einer Variablen bestehen.

Die Ein­schränkung der Form der rechten Seiten der Produktionen einer Grammatik in Greibach-Normalform beschränken also nicht die Ausdrucks­stärke der Grammatik.