Main Page | See live article | Alphabetical index

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.