<p>If $G$ is a grammar with start symbol $S$, then $G&#39;$, the augmented grammar for $G$, is $G$ with a new start symbol $S&#39;$ and production $S&#39; \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&#39; \rightarrow S$.</p>

CC BY-SA 3.0
2012-03-02T03:25:32.303Z
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
CC BY-SA 3.0
2012-03-01T22:20:28.170Z
2012-03-02T00:57:55.957Z
2012-03-02T00:57:55.957Z
mcorley
<p>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:</p>

<ol>
<li>Add a new start state pointing to the old start state</li>
<li>Eliminate Epsilon Rules</li>
<li>Eliminate Unit Rules</li>
<li>Change Long Rules into Short Ones</li>
</ol>

<p>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.</p>

<p>So for example we were told to convert the following:</p>

<p>$S \rightarrow AbA\;|\;B$</p>

<p>$B \rightarrow a\;|\;b$</p>

<p>$A \rightarrow \epsilon\;|\;a$</p>

<p>Step 1 adds the following production rule:</p>

<p>$S_0 \rightarrow S$</p>

<p>Step 2 makes the production rules become:</p>

<p>$S_0 \rightarrow S$</p>

<p>$S \rightarrow AbA\;|\;Ab\;|\;bA\;|\;b\;|\;B$</p>

<p>$B \rightarrow a\;|\;b$</p>

<p>$A \rightarrow a$</p>

<p>Step 3 makes the rules the following</p>

<p>$S_0 \rightarrow AbA\;|\;Ab\;|\;bA\;|\;b\;|\;a$</p>

<p>$S \rightarrow AbA\;|\;Ab\;|\;bA\;|\;b\;|\;a$</p>

<p>$B \rightarrow a\;|\;b$</p>

<p>$A \rightarrow a$</p>

<p>Step 4 makes the rules the following:</p>

<p>$S_0 \rightarrow A U_1\;|\;U_2 A\;|\;A U_2\;|\;b\;|\;a$</p>

<p>$S \rightarrow A U_1\;|\;U_2 A\;|\;A U_2\;|\;b\;|\;a$</p>

<p>$B \rightarrow a\;|\;b$</p>

<p>$A \rightarrow a$</p>

<p>$U_1 \rightarrow U_2 A$</p>

<p>$U_2 \rightarrow b$</p>

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

CC BY-SA 3.0
2012-03-04T12:34:21.293Z
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
CC BY-SA 3.0
2012-03-04T18:21:55.670Z
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
<fl.formal-languages><grammars><context-free>
When converting a Context-Free Grammar to Chomsky Normal Form why is a new start state added?
rhololkeolke
# When converting a Context-Free Grammar to Chomsky Normal Form why is a new start state added?

(Asked by: username_0 on 2012-03-01)

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

**Tags:** fl.formal-languages, grammars, context-free

> **Comments:**
> **username_1**: This kind of undergraduate-level questions are more suited for other SEs such as math.SE as it is stated in the FAQ.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2012-03-01. Score: 0 | Accepted 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$.

> **Comments:**
> **username_0**: So if the parser was following the CYK Parse algorithm it would only be accepted if S' was in the top of the tree?  

---

