# How to simplify context free grammars?

How to simplify this context-free grammar? $$S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b$$

Can the simplification result in this CFG?

$$S \to AC \\ S \to A \\ A \to a \\ C \to E \\ E \to b$$

• The language generated by the new grammar is $\{a,ab\}$. The old grammar can generate other words, such as $abbb$. Dec 1 '19 at 18:54
• that's what I was thinking. The languages of each grammar are not equivalent but this example is in automata theory lectures I was checking if there's a mistake. @YuvalFilmus Dec 1 '19 at 19:23
• Anyway how can we simplify this CFG @YuvalFilmus Dec 1 '19 at 19:26

Starting point: $$S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b$$ Substitute values of $$A,B,E$$: $$S \to aCD \\ C \to bD \mid \varepsilon \\ D \to C \mid b$$ Substitute values of $$D$$: $$S \to aCC \mid aCb \\ C \to bC \mid bb \mid \varepsilon$$ You can generate $$bb$$ from $$C$$ even without the rule $$C \to bb$$: $$S \to aCC \mid aCb \\ C \to bC \mid \varepsilon$$ You can generate $$b$$ from $$C$$: $$S \to aCC \\ C \to bC \mid \varepsilon$$ The language of $$C$$ is $$b^*$$, so $$CC$$ generates exactly the same words as $$C$$: $$S \to aC \\ C \to bC \mid \varepsilon$$
The grammar generates the regular language $$ab^*$$.
• You follow the algorithm for removing $\epsilon$-productions. Dec 1 '19 at 21:13