Greibachové normální forma

Z Wikipedie, otevřené encyklopedie

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  • John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (Kapitola 4.)