CFG to Chomsky normal form

I've read this part like 3-4 times and I'm not understanding what is going on.

Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The series of grammars presented illustrates the steps in the conversion. Rules show in bold have just been added. Rules shown in gray have just been removed.

Specific steps/instructions from the book

1.The original CFG G6 is shown on the left. The result of applying the first step to make a new start variable appears on the right.

S→ASA|aB         S0→S
A→B|S             S→ASA|aB
B→b|ε             A→B|S
B→b|ε

2. Remove ε rules B→ε, shown on the left, and A→ε, shown on the right.

S0→S              S0→S
S→ASA|aB|**a**        S→ASA|aB|a|**SA|AS|S** from?
A→B|S|**ε**           A→B|S|ε
B→b|**ε**             B→b

3a. Remove unit rules S→S, shown on the left, and S0→S, shown on the right.

S0→S                  S0→S|**ASA|aB|a|SA|AS**
S→ASA|aB|a|SA|AS|S    S→ASA|aB|a|SA|AS
A→B|S                 A→B|S
B→b                   B→b

3b. Remove unit rules A→B and A→S

S0→ASA|aB|a|SA|AS     S0→ASA|aB|a|SA|AS
S→ASA|aB|a|SA|AS      S→ASA|aB|a|SA|AS
A→B|S|**b**           A→S|b|**ASA|aB|a|SA|AS**
B→b                   B→b

4. Convert the remaining rules into the proper form by adding additional variables and rules. The final grammar in Chomsky normal form is equivalent to G6, which follows. (Actually the procedure given in Theorem 2.9 produces several variables Ui, along with several rules Ui→a. We simplified the resulting grammar by using a single variable U and U→a.)

S0→AA1|UB|a|SA|AS
S→AA1|UB|a|SA|AS
A→b|AA1|UB|a|SA|AS
A1→SA
U→a
B→b

I don't understand why they added the "bold" (** **) items. I also don't understand 4. Can someone please explain this to me. Thank you!

migrated from stackoverflow.comMar 11 '13 at 12:56

This question came from our site for professional and enthusiast programmers.

• You should have been given the algorithm for this. Alternatively, have a look at a textbook on the topic. – Raphael Mar 11 '13 at 15:18

Removing $\epsilon$ transitions:
Consider the rule $B\to \epsilon$. We want to remove it. To do so, we look for occurrences of $B$ in the grammar, and whenever we see on (e.g. in $S\to aB$), we add the option of choosing $B\to \epsilon$. So the rule $S\to aB$ becomes $S\to a$. Similarly, $A\to B$ becomes $A\to \epsilon$ (which we will have to remove in the next step).
Since $A\to \epsilon$ was introduced when removing $B\to \epsilon$, we now add rules where $A$ appears. For example, the rule $S\to ASA$ becomes $S\to ASA|SA|AS|S$, according to the different options of using $A\to \epsilon$ after $S\to ASA$.
In step 4 - for every rule that yields more than a pair of variables (e.g. in this case $S\to ASA$) we split this into pairs as follows. Introduce a new variable $T$, we add the rules $S\to TA$ and $T\to AS$. Then, applying these forces us to actually have $S\to ASA$.
• Do you know why they add a $S_0$ in the first step? It looks kind of useless. – Renato Sanhueza May 15 '15 at 21:47
• One property of this normal form is that the initial variable is never derived by any rule. So we add an artificial $S_0$ to ensure it's never derived. – Shaull May 16 '15 at 5:55
• One reason to add $S_0 \rightarrow S$ is in the case that the language produces the empty string $\epsilon$ (or $\lambda$). If the language doesn't produce the empty string, it's fine to have the start symbol at the right side of a production. – Seankala May 30 '18 at 14:13