Eliminating Epsilon Productions from CFG

Question

I am having a hard time figuring out how to remove the epsilon production from this context free grammar. Any help would be appreciated.
CFG: (below)

$S\to SAS|SBS|SaS|a|ba$

$A\to SAS|AaBB|Aba$

$B\to AAbB|BB$

$C\to a|bCa|Saaa$

$D\to SAS|SaS|\epsilon$

What do you mean with “remove the epsilon production”? – Dec 08 '17 at 16:56 — , Dec 08 '17 at 16:56
Translate the CFG so "epsilon" doesn't appear in D anymore – Bryce Dec 08 '17 at 17:11 — Bryce, Dec 08 '17 at 17:11

score 0 · Answer 1 · answered Dec 21 '17 at 18:24

Assuming $S$ is the start symbol. Note that $\varepsilon$ only appears in the production rule of $D$ but $S$ only references non-terminal symbols $S, A$ and $B$ (including recursive referencing). So the production rules of $C$ and $D$ are useless and can be removed. This gives us an equivalent $\varepsilon$-free CFG.

Eliminating Epsilon Productions from CFG

1 Answers1