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

Improve this question
$\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$
    – Yuval Filmus
    Commented Dec 1, 2019 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
    Commented Dec 1, 2019 at 19:23
  • $\begingroup$ Anyway how can we simplify this CFG @YuvalFilmus $\endgroup$
    – siba36
    Commented Dec 1, 2019 at 19:26

1 Answer 1

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

Improve this answer
$\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
    Commented Dec 1, 2019 at 21:12
  • $\begingroup$ You follow the algorithm for removing $\epsilon$-productions. $\endgroup$
    – Yuval Filmus
    Commented Dec 1, 2019 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
    Commented Dec 1, 2019 at 21:15
  • $\begingroup$ Just apply the algorithm. I'm not going to check that you applied it correctly. $\endgroup$
    – Yuval Filmus
    Commented Dec 1, 2019 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.