0
$\begingroup$

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.

$\endgroup$
2
  • 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
    Commented Dec 26, 2016 at 18:52
  • $\begingroup$ A context-free grammar has production rules, not transitions. Please use the correct terminology. $\endgroup$ Commented Dec 26, 2016 at 22:55

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Commented Jan 5, 2017 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
    Commented Jan 5, 2017 at 12:43
  • $\begingroup$ Note that you may be left with a single rule containing eps: S_0 -> eps. You can remove this rule altogether, but that will remove eps (empty string) from the language. There will be situations where that is what you want. $\endgroup$
    – gnasher729
    Commented Sep 20, 2022 at 10:10
0
$\begingroup$
  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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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