2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ The language generated by the new grammar is $\{a,ab\}$. The old grammar can generate other words, such as $abbb$. $\endgroup$ 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
2
$\begingroup$

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^*$.

$\endgroup$
4
  • $\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$ 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$ 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.