# Construct context-free grammar for $\{a^ib^jc^k : i\le j+k\}$

I'm looking through several of old exam sets in order to prepare for the exam and now I'm stuck on this exercise, where we have to construct a context-free grammar for the language:

$$L = \{a^ib^jc^k: i \le j+k \}$$

The best solution I've obtained so far is the following that accepts $\{a^ib^jc^k: i = j+k \}$:

\begin{align*} &S\to aSc \mid D\\ &D\to aDb \mid \epsilon \end{align*}

This context-free grammar will not create any strings that are not in the language but it will however not create all the possible strings we get with the condition $i \le j+k$.

How do I proceed to solve this?

Just allow $S$ to produce $Sc$ and $D$ to produce $Db$, as well as what you already have.

• Thanks, didn't expect it to be this simple but I've tried it on a few examples now and it works – John Oct 29 '13 at 13:22
• @John: You’re welcome. It’s just a matter of making sure that every time you generate an $a$, you also generate a $b$ or a $c$, whichever is appropriate, while leaving yourself the option of generating $b$ or $c$ on its own as well. – Brian M. Scott Oct 29 '13 at 13:31

alas..it does not work for $a^i b^j c^k$ where $i= j+k$ for

$S\rightarrow aSc|Sc|D$

$D\rightarrow aDb|\epsilon$

consider the parse tree

S

aSc

aaScc

aaSccc