Chomsky Normal Form (CNF) is a specific way of structuring context-free grammars (CFGs) in formal language theory. A context-free grammar is said to be in Chomsky Normal Form if all of its production rules meet one of the following criteria: 1. **A → BC**: A production rule where a single non-terminal symbol (A) produces exactly two non-terminal symbols (B and C).
Articles by others on the same topic
A context-free grammar is in Chomsky normal form when every production has the form or , with nonterminals and a terminal. If the empty word belongs to the language, one commonly also permits the exceptional rule under the usual restriction on the start symbol.