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$ – Yuval Filmus May 26 '18 at 14:01

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, privacy policy and cookie policy

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