An Introduction to Formal Languages and Automata, 7th Edition

6.2 TWO IMPORTANT NORMAL FORMS

There are many kinds of normal forms that we can establish for context-free grammars. Some of these, because of their wide usefulness, have been studied extensively. We consider two of them briefly.

Chomsky Normal Form

One kind of normal form we can look for is one in which the number of symbols on the right of a production is strictly limited. In particular, we can ask that the string on the right of a production consist of no more than two symbols. One instance of this is the Chomsky normal form.

DEFINITION 6.4

A context-free grammar is in Chomsky normal form if all productions are of the form

$$A\to BC$$

or

$$A\to a,$$

where A, B, C are in V, and a is in T.

EXAMPLE 6.7

The grammar

$$\begin{array}{l}S\to AS|a,\hfill \\ A\to SA|b\hfill \end{array}$$

is in Chomsky normal form. ...