Greibachové normální forma
Technology
12 hours ago
8
4
2
Author
Albert FloresGreibachové 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.)