Chomsky Normal Form Conversion Algorithm

Question

Why do we add a new start state S0 -> S when we want to convert a grammar to Chomsky normal form? What goes wrong if we do not do that?

At first I thought it's because of epsilon rules. But we do not remove an epsilon rule from start variable. So, what is benefit of adding S0 -> S?

Thanks

Answer 1

Depending on whether the empty string is in the language you might have the rule $S --> \epsilon$ (or $S_0 --> \epsilon$). This could delete an arbitrary number of symbols $S$ if these could appear on the right hand sides of rules. Because we do not want the start symbol to appear again, we introduce a new one.

This way we get exactly one more symbol per application of a rule A -> BC.

Answer 2

I think I have some explanation. If a grammar is like this:

S --> S1
S1 --> S
S1 --> a

Then, at the step of removing "unit rules" since we do not consider any specific order, we might remove S --> S1 first and we will have:

S1 --> S1
S1 --> a

and the start variable is entirely removed.