Page "Chomsky normal form" Paragraph 5

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form.

Several algorithms for performing such a transformation are known.

Transformations are described in most textbooks on automata theory, such as Hopcroft and Ullman, 1979.

As pointed out by Lange and Leiß, the drawback of these transformations is that they can lead to an undesirable bloat in grammar size.

The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side.

Using to denote the size of the original grammar, the size blow-up in the worst case may range from to, depending on the transformation algorithm used.