# 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?

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?

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).