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 $$

  • 1
    $\begingroup$ The language generated by the new grammar is $\{a,ab\}$. The old grammar can generate other words, such as $abbb$. $\endgroup$ – Yuval Filmus Dec 1 '19 at 18:54
  • $\begingroup$ 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 $\endgroup$ – siba36 Dec 1 '19 at 19:23
  • $\begingroup$ Anyway how can we simplify this CFG @YuvalFilmus $\endgroup$ – siba36 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^*$.

| cite | improve this answer | |
  • $\begingroup$ thank you very much. That is so helpful , but if I was asked just to remove epsilon-productions how can I do that? $\endgroup$ – siba36 Dec 1 '19 at 21:12
  • $\begingroup$ You follow the algorithm for removing $\epsilon$-productions. $\endgroup$ – Yuval Filmus Dec 1 '19 at 21:13
  • $\begingroup$ would the result be something like this: S-->A|AC|AD|ACD A-->a C-->E|ED D-->C|b E-->b $\endgroup$ – siba36 Dec 1 '19 at 21:15
  • $\begingroup$ Just apply the algorithm. I'm not going to check that you applied it correctly. $\endgroup$ – Yuval Filmus Dec 1 '19 at 21:15

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.