Rules regarding Chomsky Normal Form (CNF) grammars I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions:


Can I use a single variable (a non-terminal) on the left-hand side of multiple rules?
Can I use a single variable (a non-terminal) twice on the right-hand side of a single rule?


For instance, is the following grammar properly in Chomsky Normal Form?  Is it OK that I have two rules with $S$ on the left-hand side?  Is it OK that I have $X$ twice on the right-hand side of the second rule?

$$S_0 \to S$$
$$S \to XX$$
$$S \to XZ$$
$$\vdots$$
The production

$$S_0 \to S$$

is not in CNF. CNF requires that nonterminals produce either two nonterminals or one terminal. Since the above line shows a nonterminal producing a single nonterminal, it does not fit. The CFG in CNF would be just:

$$S_0 \to XX$$
$$S_0 \to XZ$$
$$\vdots$$

To answer your original questions, though, yes, you can do the above in CNF. There are no stipulations about how many times a nonterminal may appear on the left or whether it can be duplicated on the right.