Erasing $\epsilon$ production from CFG

Question

I would like to delete the $\epsilon$-production from the context free grammar with the following rules P:

$$S \rightarrow ASB , BSA, \epsilon$$ $$A \rightarrow aS$$ $$B \rightarrow bB, b$$

Now we were only given this algorithm for that task:

1. collect all variables from which the empty word is derivable.

-> which in this case is only S

2. Add to the new rules P' every rule $A \rightarrow \alpha'$, with $\alpha \neq \epsilon$, for which P had a rule $A \rightarrow \alpha$, so that $\alpha'$ results from $\alpha$ by erasing all variables that were collected in step 1.

In this case I would erase $S \rightarrow \epsilon$ and since P included $A \rightarrow aS$ I would add $A \rightarrow a$ to P', giving me:

$$S \rightarrow ASB , BSA$$ $$A \rightarrow a$$ $$B \rightarrow bB, b$$

The grammar with these rules does not, however yield the same language as P, in fact the S never disappears. Can anybody please tell me what I'm doing wrong and how to do it correctly?

Answer 1

You cannot erase the $ϵ$-production from this grammar and keep the same language. The reason is that since you have the production $S\to ϵ$, the language contains $ϵ$. And the only way a CF language can contain $ϵ$ is with an $ϵ$-production.

Answer 2

Keep the old productions, you add new rules. Some occurrences of $S$ may lead to a nonempty string while other occurrences might lead to nothing, so you need both old and new in general.

Also erase $S$ from the right hand side of productions for $S$ itself.

Thus the new rules now are

$$S \rightarrow ASB , BSA, AB , BA$$ $$A \rightarrow aS, a$$ $$B \rightarrow bB, b$$