A context-free language is defined by its description:

$L=(a^{2k} \space b^n \space c^{2n} \mid k \geq 0, \space n > 0)$

For example:

$bcc, aabcc, aabbcccc, bbcccc$

How to build a context-free grammar for this context-free language?

I suppose that the order for generating any chain in this problem matters: 'b' will always stand after 'a' and 'c' - after 'b'. Is it so?

My attempts leaded to this solution:

$ S \rightarrow aaAbcc \mid bAcc \mid aabAcc $

$ A \rightarrow aa \mid bcc \mid λ $

Please correct me if I'm wrong or better offer your solution to this problem.

  • $\begingroup$ Why? This is a concrete problem that has its own conditions and solution and differs from the examples offered in that topic. $\endgroup$ – Happy Torturer May 19 '14 at 8:29

$ S \rightarrow EG $ , $ E \rightarrow aO \mid λ $ , $ O \rightarrow aE $ , $ F \rightarrow bFcc \mid λ $, $ G \rightarrow bFcc $ . I am assuming $λ$ stands for empty string.

Better one:

$ S \rightarrow EF $ , $ E \rightarrow aO \mid λ $ , $ O \rightarrow aE $ , $ F \rightarrow bFcc \mid bcc $.

  • $\begingroup$ Thank you, it seems to me it's correct! But is it possible to move some conditions (including terminals) in the S rule? Like I was trying to do. $\endgroup$ – Happy Torturer May 17 '14 at 9:46
  • $\begingroup$ I was unable to move terminals to S because of the fact that number of a's and b's can be different. Although you may try it. If you are able to move them please let me know. $\endgroup$ – preetsaimutneja May 17 '14 at 9:58
  • 2
    $\begingroup$ Slightly simpler, $S\rightarrow EF, E\rightarrow aaE \mid \lambda, F\rightarrow bFcc \mid bcc$. $\endgroup$ – Rick Decker May 18 '14 at 0:35

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