Greibachové normální forma

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 \lambda$

kde A je neterminál, α je terminál, S je startovací neterminální symbol, X je (případně prázdná) sekvence neterminálních symbolů (ve které se nevyskytuje S) 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é.

[editovat] Související články

[editovat] Reference

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

Kategorie: Formální jazyky

Greibachové normální forma v jiných jazycích: Bosanski, Deutsch, English, Hrvatski, 日本語, Nederlands, Polski, Română, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Greibachov%C3%A9_norm%C3%A1ln%C3%AD_forma“
Stránka byla naposledy upravena v Stránka byla naposledy editována 26. 8. 2008 v 14:28.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).