[Solved]: Rules regarding Chomsky Normal Form (CNF) grammars

Problem Detail: 

I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions:

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

2. 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$$

Asked By : haunted85

Answered By : robyoder

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18052