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

15.6k Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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