English Dictionary

Chomsky Normal Form

名詞

不可算名詞

(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.

日本語の意味

ショムスキー正規形：計算理論における文脈自由文法の一形式であり、各生成規則の右辺が単一の終端記号または二つの非終端記号のみで構成されるもの

To simplify parsing algorithms, we first convert the grammar into Chomsky Normal Form and then run the parser.

解析アルゴリズムを簡略化するために、まず文法を各生成規則の右辺が一つの終端記号または二つの非終端記号であるような文脈自由文法の形式（チョムスキー正規形）に変換してからパーサを実行します。

意味（1）

(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.

意味（2）

(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.)