I'm trying to come up with a context-free grammar for the following language:

$$L = \{a^mb^nc^{m+n}\mid 0 \le n \le m\}$$

My thinking is that i can rewrite this to

$$L = \{a^mb^nc^nc^m\mid 0 \le n \le m\}$$

and then create the grammar

$$ \begin{align*} S &\rightarrow aSc \mid B\\ B &\rightarrow bBc \mid \epsilon \end{align*} $$

The problem is that this grammar doesn't capture $0 \le n \le m$ and I can't figure out how to do this. Any help would be greatly appreciated.

  • 2
    $\begingroup$ Are you sure your language is context-free? $\endgroup$ Commented May 26, 2018 at 14:01

1 Answer 1


Hint: is the language $L' = \{a^n b^n c^{2n} \mid n \ge 0\}$ context-free?


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.