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

  • 1
    $\begingroup$ This kind of undergraduate-level questions are more suited for other SEs such as math.SE as it is stated in the FAQ. $\endgroup$ – Juan Bermejo Vega Mar 4 '12 at 12:34
  • $\begingroup$ 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. $\endgroup$ – Kaveh Mar 4 '12 at 18:21

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.