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 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 which 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, an US linguist that invented the Chomsky hierarchy.