 Chomsky normal form

A context-free grammar is in Chomsky normal form when every production has the form $A\to BC$ or $A\to a$, with $A,B,C$ nonterminals and $a$ a terminal. If the empty word belongs to the language, one commonly also permits the exceptional rule $S\to ϵ$ under the usual restriction on the start symbol.

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