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:
- collect all variables from which the empty word is derivable.
-> which in this case is only S
- 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?