0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\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
    Commented May 19, 2014 at 8:29

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented May 17, 2014 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$
    – donkey
    Commented May 17, 2014 at 9:58
  • 2
    $\begingroup$ Slightly simpler, $S\rightarrow EF, E\rightarrow aaE \mid \lambda, F\rightarrow bFcc \mid bcc$. $\endgroup$
    – Rick Decker
    Commented May 18, 2014 at 0:35

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