Chomsky normal form

A formal grammar is in Chomsky normal form iff all production rules are of the form:

A → BC or

A → α

where A, B and C are nonterminal symbols and α is a terminal symbol.

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar which does not generate the empty string can be transformed into an equivalent one which is in Chomsky normal form.

The Chomsky normal form of a context-free grammar is important because it yields efficient algorithms. For example, the CYK algorithm that decides whether a given string can be generated by a given grammar uses the Chomsky normal form.

The Chomsky normal form is named after Noam Chomsky, the US linguist who invented the Chomsky hierarchy.