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?

Thanks for answers and help.

  • 2
    $\begingroup$ "Can you please check my answer" is not a good question for this site. The answer isn't interesting to anyone but yourself. $\endgroup$
    – adrianN
    Dec 26 '16 at 18:52
  • $\begingroup$ A context-free grammar has production rules, not transitions. Please use the correct terminology. $\endgroup$ 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.

  • $\begingroup$ 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$. $\endgroup$ Jan 5 '17 at 0:08
  • $\begingroup$ Yes exactly, yours is a better description of the process. Also if you did already remove $R \to \varepsilon$, then don't add back. $\endgroup$
    – CPUFry
    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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.