Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')

Question

I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\{S,A,B,C\},\{0,1\},P,S)$, where the productions are

\begin{align} &S \to AB \mid C \\ & A \to 0A1 \mid \epsilon \\ &B \to 0B \mid 0 \\ &C \to 0C0 \mid B \end{align}

The result of applying the remove ϵ rules algorithm is:

\begin{align} &S \to B \mid C \mid AB \\ &A \to 0A1 \\ &B \to 0B \mid 0 \\ &C \to 0C0 \mid B \end{align}

but then, when I re-apply the remove redundant symbols algorithm (as I should do) I get:

\begin{align} &S\to B \mid C \\ &B \to 0B \mid 0 \\ &C \to 0C0 \mid B \end{align}

(as $A \Rightarrow^*$ will never result in a terminal word)

The problem is, that $010$ is generated by the original grammar but not by the latter grammar.

in fact, not a single word that contains 1 in it belongs to the latter grammar, as 1 could only have been achieved via $A$!

What have I done wrong? Why are the two grammars producing different languages? They are supposed to be the same.

Answer 1

This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make sure that the algorithm you are applying is 100% correct, and that you are following it 100% accurately.

How does the $\epsilon$-removal work? Suppose that we want to remove the production $A \to \epsilon$. How can this production be used in a derivation? Whenever $A$ appears on the right-hand side of a production, we can remove it by applying $A\to\epsilon$. Hence, in order to get rid of the production $A\to\epsilon$, we simply replace each production $X \to \alpha$ by all possible productions obtained by removing occurrences of $A$ in $\alpha$. (This may result in productions of the form $X \to \epsilon$, which we need to handle separately.)

In your case, this means that we need to augment the production $A \to 0A1$ with the production $A \to 01$ obtained by erasing $A$ on the right-hand side.

What is a good way of finding such bugs? You describe three grammars: the original one, the one obtained after removing $\epsilon$ productions, and the final one obtained by removing redundant symbols. The first one generates $010$, the last one doesn't. The first step is to check which of the two transformations introduced the mistake, and you can do that by checking whether the second grammar generates $010$.

It turns out that the second grammar doesn't generate $010$. In order to understand what went wrong, you can take a derivation of $010$ in the first grammar, and see why it cannot be reproduced in the second grammar. One such derivation is $S \to AB \to 0A1B \to 0A10 \to 010$. In the second grammar, all but the last steps are still available, so the problem lies with the production $A \to \epsilon$, which the second grammar isn't able to simulate.

Answer 2

You already lost the $010$ word when you've removed the $A\to \epsilon$ rule. In $G'$, which is the grammar you got by removing $\epsilon$-rules, you also need to add the $A \to 01$ rule.