Chomsky Normal Form (thing)

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