Converting to chomsky normal form, eliminating epsilon

Question

I have a following CFG rule :

• S -> BSA | epsilon
• A -> abC | a | c
• B -> baC | b | epsilon
• C -> aCc | AB | epsilon

I am on the epsilon elimination stage of the algorithm, I have eliminated following eplsions C -> epsiolon, B -> epsilon and here is what i got so far :

• S_0 -> S
• S -> BSA | SA | epsilon
• A -> abC | a | c| ab
• B -> baC | b | ba
• C -> aCc | AB | ac| A Should I also eliminate S-> epsilon(shown in bold) since S is the original start variable?

Should I also copy the epsilon to S_0 at the unit rule stage of the algorithm?

Answer 1

I your first grammar, You can derive epsilon from S. So the empty word belong to the described language. Therefore you must have a epsilon in the second equivalent grammar. Now in a normal form grammar, when there is a derivation S -> epsilon, then S can't appear on the right of a derivation. So the rule

S -> BSA | SA | epsilon

is not allowed is a Chomsky normal form. So you probably want something as

S_0 -> S | epsilon      // initial
S -> BA | A | BSA | SA
[...]