Chomsky Normal Form (CNF) is a restriction on the form of context-free grammars: the right hand side of every rule must consist of either one terminal or two nonterminals.

It is indeed a normal form: algorithms exist to convert any context-free grammar into an equivalent grammar in CNF. But it is not possible to speak of "the Chomsky Normal Form of a context-free grammar": different normalization algorithms produce different results.

Also, many different grammars can produce the same normal form. (For these reasons, it is incorrect to say that a CNF grammar "describes" a context-free grammar, and I've /msged PeterPan asking to correct this.)

There is one caveat: grammars in CNF cannot generate the empty string, so they can only represent arbitrary grammars up to the empty string.

An obvious normalization algorithm:

1. recursively expand all empty-generating rules
2. for each terminal, introduce a nonterminal to generate it, and replace all terminals occurring as part of existing right hand sides with those nonterminals
3. recursively replace all rules A -> BX, where A, B are nonterminals and X is a string of 2 or more nonterminals, with the rules A -> BC and C -> X, where C is a new nonterminal

For example: in grammar

``````

S -> a
S -> aAS
A -> a
A -> b
A -> SS
A ->

``````
we eliminate the empty rules (all one of them) to get
``````

S -> a
S -> aAS
S -> aS
A -> a
A -> b
A -> SS

``````
then eliminate non-isolated terminals (all one of them) to get
``````

S -> a
S -> CAS
S -> CS
A -> a
A -> b
A -> SS
C -> a

``````
and finally "chain" the long right hand sides (all one of them) to get a grammar in CNF:
``````

S -> a
S -> CD
S -> CS
A -> a
A -> b
A -> SS
C -> a
D -> AS

``````