Give a context-free grammar that generates the language

Question

Give a context-free grammar that generates the language:

$\{a^i b^j c^k d^h \mid i, j, h \geq 0, k>0 \text{ and } i+j \leq h\}$

This is what I've done so far:

$S \rightarrow aSb \mid bSc \mid cSd \mid D$

$D \rightarrow dD \mid d$

Answer 1

Your construction fails to make sure that the $a$'s stay in front of the $b$'s, note that it allows $S \to bSc \to baSbc \to baDbc \to badbc$. This example also shows that you need to make sure there are at least as many $d$'s as $a$'s and $b$'s combined.

The following rules should work: $$ S \to aSd \mid T \\ T \to bTd \mid U \\ U \to Ud \mid cU \mid c $$ Note how the rules $S \to aSd, T\to bTd$ ensure that $i+j \le h$, and the addition of the intermediate nonterminal $T$ makes sure the $a$'s are all in front of the $b$'s.