Greibachové normální forma

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Graibachové 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. 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.)