When converting a Context-Free Grammar to Chomsky Normal Form why is a new start state added? [closed]

Question

I'm taking a theoretical computer science class and we just went over the steps to rewrite a context-free grammar in Chomsky Normal Form. The steps we were told to complete are:

1. Add a new start state pointing to the old start state
2. Eliminate Epsilon Rules
3. Eliminate Unit Rules
4. Change Long Rules into Short Ones

I think I understand how to do each rule, but I'm not seeing the reason for step 1 as the examples we did in class all led to the new starting state being equal to the old starting state because of step 3 when the unit rules were eliminated. Perhaps I'm misunderstanding something so I'll give the example that was given in class.

So for example we were told to convert the following:

$S \rightarrow AbA\;|\;B$

$B \rightarrow a\;|\;b$

$A \rightarrow \epsilon\;|\;a$

Step 1 adds the following production rule:

$S_0 \rightarrow S$

Step 2 makes the production rules become:

$S_0 \rightarrow S$

$S \rightarrow AbA\;|\;Ab\;|\;bA\;|\;b\;|\;B$

$B \rightarrow a\;|\;b$

$A \rightarrow a$

Step 3 makes the rules the following

$S_0 \rightarrow AbA\;|\;Ab\;|\;bA\;|\;b\;|\;a$

$S \rightarrow AbA\;|\;Ab\;|\;bA\;|\;b\;|\;a$

$B \rightarrow a\;|\;b$

$A \rightarrow a$

Step 4 makes the rules the following:

$S_0 \rightarrow A U_1\;|\;U_2 A\;|\;A U_2\;|\;b\;|\;a$

$S \rightarrow A U_1\;|\;U_2 A\;|\;A U_2\;|\;b\;|\;a$

$B \rightarrow a\;|\;b$

$A \rightarrow a$

$U_1 \rightarrow U_2 A$

$U_2 \rightarrow b$

$S_0$ just ends up being the same production rule as $S$ so why did we need it in the first place? Is there a case where $S_0$ won't produce the same output as $S$? Also since no state ever goes to S when it starts from the initial state $S_0$ is it okay to get rid of $S$?

Answer 1

If $G$ is a grammar with start symbol $S$, then $G'$, the augmented grammar for $G$, is $G$ with a new start symbol $S'$ and production $S' \rightarrow S$. The purpose of this new starting production is to indicate to the parser when it should stop parsing and announce acceptance of the input. That is, acceptance occurs when and only when the parser is about to reduce by $S' \rightarrow S$.