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!