Greibachové normální forma

Greibachové normální forma (GNF) je tvar formální gramatiky, ve které mají všechny odvozující pravidla tvar:

$A\to \alpha X$

nebo

$S\to ϵ,$

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 $S\to ϵ,$ ) 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. Šablona:ISBN. (Kapitola 4.)