# Removing epsilon transition from context-free grammar

I have the following context-free grammar from which I have to remove epsilon transitions:

$S \to 0A0|0$

$A \to BC|2| CCC$

$B \to 1C | 3D | \epsilon$

$C \to AA3 | \epsilon$

$D \to AAB | 2$

By algorithm, I create $N_{0}$ that will hold all non-terminals that contain $\epsilon$ and in next steps add non-terminals that have rule that contains only non-terminals from the previous iteration of N e.g.

1. $N_{0} = \{\}$

2. $N_{1} = \{B,C\}$

3. $N_{2} = \{B,C,A\}$

4. $N_{3} = \{B,C,A,D,S\}$

Now I have to adjust rules, we can remove non-terminals in $N_{3}$ object from rules, thus we have to create all combinations without it e.g.

$S \to 0A0 | 00 | 0$

$A \to BC | B | C | CCC | CC$

$B \to 1C | 1 | 3D | 3$

$C \to AA3| A3 | 3$

$D \to AAB | AA | A | AB | B | 2$

We see that no non-terminal isn't useless, so is this the final context-free grammar? Or did I make mistake somewhere?

• "Can you please check my answer" is not a good question for this site. The answer isn't interesting to anyone but yourself. Dec 26 '16 at 18:52
• A context-free grammar has production rules, not transitions. Please use the correct terminology. Dec 26 '16 at 22:55

As described in the algorithm to put a given CFG in Chomsky Normal Form:

To remove the $\varepsilon$-rules: Remove a rule $A \to \varepsilon$ if $A \neq S_0$ ($S_0$ being the start-variable). To 'repair' the CFG, add for every occurence of $A$ in the body of a rule, the same rule but with $A$ removed. Example: if you have rules $A \to B | \varepsilon$ and $B \to BAAB$. To remove the $\varepsilon$ for $A$, add for each ocurrence of A a new rule with A removed. In this case: $A\to B$ (remove $\varepsilon$) and $B \to BAAB|BAB|BB$.

Finally, for rules of the form $R \to A$, add $R\to \varepsilon$ if you did not remove $R \to \varepsilon$ in a previous iteration.

• And what if you did already remove $R\to\epsilon$? Also, I think you mean to add a new rule for each subset of occurrences of $A$. For example, if the rule was actually $B\to ACA$, you'd need to replace that with $B\to ACA|CA|AC|C$. Jan 5 '17 at 0:08
• Yes exactly, yours is a better description of the process. Also if you did already remove $R \to \varepsilon$, then don't add back. Jan 5 '17 at 12:43
1. Remove all useless symbols( all non productive non terminals excluding the production rule)
2. Remove all unreachable ( non terminals that can’t be reached from the production rule or starting rule)
3. Finally apply the removals of the epsilon rule to all rules that contain them.