I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers.

Also, in general, are there any good methods or ways of thinking that help one to think of context free grammars that generate a given language. Any tips are much appreciated, thanks.

EDIT: I've tried S →ABCD, A →aA | λ, B →bB | λ, C →ccC | λ, D →dD | λ

However, this doesn't allow for always generating twice the amount of c's as there are a's.

  • 1
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby Jan 4 '15 at 18:51
  • $\begingroup$ For me, it always helps how to imagine how a corresponding derivation tree looks like. Also, it is useful to identify what "parts" of a word depend on each other and, hence, might need to be generated with the same rule. $\endgroup$ – Dan Jan 4 '15 at 18:53
  • $\begingroup$ I'm stuck on matching the a's and c's and I've added on what I tried to the original post. And thank you Dan, I'll try and use those methods. $\endgroup$ – AmazingBergkamp Jan 4 '15 at 19:25

For matching number of a and c you need to do something like this:

$$ S \rightarrow AB \\ A \rightarrow aAcc \\ A \rightarrow C \\ C \rightarrow bC | λ \\ B \rightarrow dB | λ $$

You need to produce them in one rule to be sure the ratio is kept.


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