# Erasing $\epsilon$ production from CFG

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

1. 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?

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.
• Thank you. Would I be able to reproduce $L(G)-\{\epsilon\}$, where G is the original grammar, without $S \rightarrow \epsilon$? – eager2learn Feb 16 '15 at 15:08
• Yes. You can always do that (see beginning of CNF conversion). You indeed collect all variables deriving on $ϵ$. Then for any production $X\to\xi$, you take each combination of occurences of these variables in $\xi$ and make a new production by erasing them. You add these new productions to the grammar, and you remove the $ϵ$-productions. – babou Feb 16 '15 at 15:58
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.
$$S \rightarrow ASB , BSA, AB , BA$$ $$A \rightarrow aS, a$$ $$B \rightarrow bB, b$$