Chomsky Normal Form
Hello, you have come here looking for the meaning of the word Chomsky Normal Form. In DICTIOUS you will not only get to know all the dictionary meanings for the word Chomsky Normal Form, but we will also tell you about its etymology, its characteristics and you will know how to say Chomsky Normal Form in singular and plural. Everything you need to know about the word Chomsky Normal Form you have here. The definition of the word Chomsky Normal Form will help you to be more precise and correct when speaking or writing your texts. Knowing the definition ofChomsky Normal Form, as well as those of other words, enriches your vocabulary and provides you with more and better linguistic resources.
English
Etymology
Named after Noam Chomsky (b. 1928), American linguist and philosopher, who first described it.
Noun
Chomsky Normal Form (uncountable)
- (computing theory) A 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.
- (computing theory) A 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.)