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?
Best Answer
Just allow $S$ to produce $Sc$ and $D$ to produce $Db$, as well as what you already have.