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

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$?

## closed as off topic by Suresh VenkatMar 4 '12 at 22:40

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

• This kind of undergraduate-level questions are more suited for other SEs such as math.SE as it is stated in the FAQ. – Juan Bermejo Vega Mar 4 '12 at 12:34
• Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. – Kaveh Mar 4 '12 at 18:21

## 1 Answer

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

• So if the parser was following the CYK Parse algorithm it would only be accepted if S' was in the top of the tree? – rhololkeolke Mar 2 '12 at 3:25