Cheap and Secure Web Hosting Provider : See Now

# [Answers] Erasing $\epsilon$ production from CFG

, ,
Problem Detail:

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.