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.

  • $\begingroup$ Thanks, didn't expect it to be this simple but I've tried it on a few examples now and it works $\endgroup$ – John Oct 29 '13 at 13:22
  • $\begingroup$ @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. $\endgroup$ – 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







fail... the solution is quite a bit more interesting but since I give it as an assignment I will cruelly keep it a secret..


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.