# Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not

I'm having trouble with this particular language: $$\{a^i b^j c^k \mid i+j \le k\}$$

If it's not context-free, I don't know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I don't know how to create a context-free grammar that generates this language.

Which one applies? Can you help me out?

• Keep trying. Try both possibilities until one of them works. Dec 11, 2013 at 16:59
• Suppose you had to generate such a string from the outside in (the first and last characters first, then the second and second-last, etc.) How might you do it? Dec 11, 2013 at 17:20
• Awesome hint, Niel. It's clearer now.
– gbag
Dec 11, 2013 at 18:29

Hint. $k = i + j + ?$, so the language is $a^ib^jc^?c^jc^i$.
$$\begin{eqnarray} S & → & AC \\ AC & → & a \; AC \; c & \mid & BC \\ BC & → & b \; BC \; c & \mid & EC \\ EC & → & \varepsilon \; EC \; c & \mid & \varepsilon \end{eqnarray}$$
The $$\varepsilon$$ in the first RHS of $$EC$$ is of course not necessary, but it highlights a certain symmetry.
• I've added the adjective "context-free", from which one can infer that all the left-hand sides consist of a single non-terminals. One can then infer that some non-terminals' names consist of multiple letters. I tried renaming $S$ to $START$ to hit people on the nose with that fact, but it looks ugly (at least in the preview). Jun 24, 2019 at 11:19