Q:

Is the language $a^i b^j c^k$ with $i+j > k$ context-free?

I am learning about Context Free Grammars and currently stuck on the following question.

Is the following language context-free? If not, then how can we prove it using Pumping Lemma?
$\qquad L = \{a^i b^j c^k \mid i,j,k \geq 0 \land i+j > k\}$.

After spending some time I have been able to generate the production rules for the following language, but unable to understand and conclude the above.
Important Condition ($i+j = k$)

$\qquad M = \{a^i b^j c^k \mid i,j,k \geq 0 \land i+j = k\}$.

$\qquad\begin{align*}
  S &\to aSc \mid X \\
  X &\to bXc \mid ε
\end{align*}$
Any assistance in solving the condition ($i+j > k$) would be a great help.  

A:

There is a simple way to obtain a grammar for the language $L_{\geq} = \{a^ib^jc^k : i+j \geq k\}$ given a grammar for the language $L_= = \{a^ib^jc^k : i+j = k\}$. Starting with a grammar for $L_=$, change all rules mentioning $c$ to rules mentioning a new non-terminal $C$, and add the two productions $C\to c \mid \epsilon$.
Concretely, if we start with the following grammar for $L_=$:
$$
\begin{align*}
&S\to aSc \mid T \\
&T\to bTc \mid \epsilon
\end{align*}
$$
then the corresponding grammar for $L_{\geq}$ is
$$
\begin{align*}
&S\to aSC \mid T \\
&T\to bTC \mid \epsilon \\
&C\to c \mid \epsilon
\end{align*}
$$
Of course, this is not quite the restriction we were after. It is possible to modify the grammar for $L_{\geq}$ to a grammar for $L_{>} = \{a^ib^jc^k : i+j > k\}$ by "signalling" within the grammar that at least one $c$ was actually dropped. This requires duplicating some of the non-terminals and rules. Details left to you.
Another modification which will produce $L_{\geq}$ from $L_=$ replaces each $a$ by a non-terminal that generates $a^+$, and each $b$ by a non-terminal that generates $b^+$:
$$
\begin{align*}
&S\to ASc \mid T \\
&T\to BTc \mid \epsilon \\
&A \to Aa \mid a \\
&B \to Bb \mid b
\end{align*}
$$
Again we can use signalling to get $L_>$ rather than $L_{\geq}$. Details left to you.

