Meanings
- uncountablecomputingA context-free grammar in which the right hand side of any production rule consists of either one terminal symbol or two non-terminal symbols.
Any ε-free Context Free Grammar can be converted (through an algorithm) into one in Chomsky Normal Form, and there is an algorithm that can parse formulas in the language of such a grammar in polynomial time; it is called the CYK algorithm.
- uncountablecomputingA context-free grammar in which the right hand side of any production rule consists of either one terminal symbol or two non-terminal symbols (neither of which is the start symbol) or the epsilon (i.e. null string) symbol, but only if the left hand side is the start symbol. (Note: this is the full-fledged version, whereas the previous definition may be said to be defining Chomsky reduced form.)
Origin
Named after Noam Chomsky (b. 1928), American linguist and philosopher, who first described it.
Full word history & related roots →Cite this entry
Chomsky Normal Form. (n.d.). In WatkinsX Dictionary. Retrieved November 3, 2026, from https://dictionary.watkinsx.com/word/Chomsky%20Normal%20Form
“Chomsky Normal Form.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/Chomsky%20Normal%20Form. Accessed November 3, 2026.
WatkinsX Dictionary, s.v. “Chomsky Normal Form,” accessed November 3, 2026, https://dictionary.watkinsx.com/word/Chomsky%20Normal%20Form.
Source: Chomsky Normal Form on Wiktionary, CC BY-SA 4.0.