Greibachové normální forma (GNF) je tvar formální gramatiky, ve které mají všechny odvozující pravidla tvar:
nebo
kde A je neterminál, α je terminál, S je výchozí neterminální symbol, X je (případně prázdná) posloupnost neterminálních symbolů (ve které se nevyskytuje S, pokud gramatika obsahuje pravidlo ) a ɛ je prázdný řetězec.
Gramatika v Greibachové normální formě postrádá levou rekurzi. Každá bezkontextová gramatika může být transformována do Greibachové normální formy. Forma je pojmenovaná podle její autorky Sheily Greibachové.
Související články Backusova–Naurova forma Chomského normální forma Kurodova normální forma
Reference John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. . (Kapitola 4.)
Kategorie:Formální jazyky