Chomsky normální forma

formální gramatika je v Chomsky normální formě iff všechna pravidla výroby jsou formy:

-> BC nebo

-> a alpha;

kde, B a C jsou symboly nonterminal a a alpha; je symbol terminálu.

Každá gramatika v Chomsky normální je kontext-volný, a naopak, každý kontext-volná gramatika, která netvoří prázdný řetězec může být transformována do ekvivalentu jeden který je v Chomsky normální formě.

Chomsky normální forma kontextu-volná gramatika je důležitá, protože to dá účinné algoritmy. Například, CYK algoritmus který se rozhodne zda daný řetězec může být vytvořen danou gramatikou používá Chomsky normální formu.

Chomsky normální forma je jmenována po Noam Chomsky, americký lingvista, který vynalezl Chomsky hierarchii.