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 \epsilon, 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 \epsilon, ) 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. +more 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