How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?

Question

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?

I don't have much idea how to approach this one. Could some help me to understand how to approach these kinds of problem?

Answer 1

HINT: You want all words of the form $uvw$, where $u\in\{a^nb^n:n\ge 0\}$, $v\in\{b^n:n\ge 1\}$, and $w\in\{b^nc^n:n\ge 0\}$. Each of those types is easy to generate with a context-free grammar. If that’s not enough, a slightly bigger hint is spoiler-protected below; mouse-over to see it.

You have to generate at least one $b$. After that, every time you generate an $a$ or a $c$, you must also generate a $b$. Try starting with a production $S\to AbBC$, where $B$ generates the language corresponding to the regular expression $b^*$, $A$ generates $\{a^nb^n:n\ge 0\}$, and ... ?