Eliminating Epsilon Productions from CFG

863 Views Asked by At

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$

1

There are 1 best solutions below

0
On

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.