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.

An epsilon production is a grammar production whose right-hand side is the empty word.

A unit production replaces one nonterminal by one nonterminal and emits no terminal symbols.

To convert a context-free grammar to Chomsky normal form, first add a fresh start symbol. Remove epsilon productions, retaining the exceptional start production only when the empty word is to remain in the language; then remove unit productions and symbols that cannot participate in a terminal derivation. Replace each terminal occurring in a right-hand side of length at least two by a new nonterminal that produces that terminal. Finally split every right-hand side of length greater than two into binary productions using fresh nonterminals.

A Chomsky-normal-form parse tree for a word of length $n\ge 1$ has $n$ terminal productions and $n-1$ binary productions. Every derivation represented by the tree therefore has exactly $2n-1$ steps.

The CYK algorithm decides membership in a context-free language given by a grammar in Chomsky normal form. It records, for every substring, the nonterminals that derive that substring and combines adjacent substrings using binary productions. For a word of length $n$ and a fixed grammar, it runs in $O(n^3)$ time.

Weak Chomsky normal form additionally permits ternary productions $A\to BCD$. Compressing a two-step pattern $A\to BE$, $E\to CD$ into $A\to BCD$ preserves its generated yields whenever the intermediate variable has no other role, and saves one derivation step each time the pattern is used.