Chomsky normal form

Summary

A context-free grammar is in Chomsky normal form when each rule either replaces a nonterminal by two nonterminals or by one terminal letter. Every context-free language has a grammar in this form. The rigid shape makes parse trees binary, which simplifies proofs such as the pumping lemma and algorithms such as CYK parsing.