How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's?

Question

Give Context-free Grammar for the language $\{a^i b^j c^k d^h \mid i,j,h \ge 0, k>0, i+j \le h\}$

This is a training exercise, for which we don't get any answers, in a course I'm taking. I have found similar examples, but nothing that touches on the i+j≤h part of this. My biggest trouble is that it is ordered, so I have no idea how to add d's to the end when I add a's or b's to the front. I haven't gotten very far because of this, but my thinking looks like this at the moment:

S→ABcCD
A→aA | ϵ
B→bB | ϵ
C→cC | ϵ
D→dD | ϵ

I can't put things like A→aAd or A→aBCD because that would result in c's and d's before b's in the end word/string. My conclusion is that I am probably on the wrong track, but all examples I find use some sort of partitioning like this.

So could anyone point me in the right direction?

Answer 1

There are lots of answers on this site about this subject. See, for example here and here. The underlying idea that often works for problems like this is to work from the inside out.

1. The $c^k$ part is easy: just use the production $V\rightarrow cV\mid c$.
2. The part surrounding the $c^k$ part consists of a bunch of $b$s followed by an equal number of $d$s. That's also easy; it can be generated by $U\rightarrow bUd$. Once we're finished with that, we switch to the $c$ part, so we have $U\rightarrow bUd\mid V$.
3. Keep going. Now you want to surround that part with a bunch of $a$s followed by the same number of $d$s. With what we've done so far, you should be able to do this part.
4. Finally, we want $i+j\le h$ so we concatenate the strings we've generated so far with zero or more extra $d$s. See hint (1).

As with many subjects, it gets easier the more examples you've done. Just keep at it.