I tried to solve it by this:$$\big\{a^ib^jc^k\mid k> i+j\text{ and }i,j,k \ge0\big\}\cup\big\{a^ib^jc^k\mid k< i+j\text{ and }i,j,k \ge0\big\}$$
So, $$S_0\to S_1|S_4$$
$$\\ S_1\to S_2c
\\S_2 \to S_2c|aS_2c|S_3
\\S_3 \to S_3c|bS_3c|\varepsilon$$
$$\\ S_4\to aS_5
\\S_5 \to aS_5|aS_5c|S_6
\\S_6 \to bS_6|bS_6c|\varepsilon$$
For general, I don't know how to check that my solution is right for all cases.
For instance, the string $bb \in L$ but I don't know how to create it, so I need help solving it.
Thanks.
Best Answer
The part of the grammar for $S_4$ that is supposed to generate the second subset of the language is wrong because $S_4$ always derives a string that starts with $a$. You can split it up into cases: one starts with $a$ and the other starts with $b$.
\begin{gather*} S_4\to aS_5|bS_6\\ S_5 \to aS_5|aS_5c|S_6\\ S_6 \to bS_6|bS_6c|\varepsilon \end{gather*}
I think the easiest way to prove this is by what's called structural induction. I'm going to show that $S_4$ generates the second subset of the language. Then you can try to mimic to prove that $S_1$ generates the first subset of the language.
Let's number the rules to make this easier: 1.1, 1.2, 2.1, 2.2, 2.3, 3.1, 3.2, 3.3. (The format is row-number.column-number)
To prove that $S_4$ generates the second subset of the language, you need to prove 2 directions: for any string $s$ in the subset, there's a derivation from $S_4$ to $s$; and any string derived by $S_4$ is in the subset.
One direction:
Let $s = a^mb^nc^k$ with $m + n > k$. Then come up with a specific derivation for $s$ from $S_4$. Split this into cases.
If $m = 0$, apply 1.2 once, 3.2 $k$ times, $3.1$ $n-k$ times, then 3.3.
If $m > 0$, apply 1.1, 2.2 $x=\min(k,m-1)$ times, 2.1 $\max(0, m-1-x)$ times, 3.2 $y = \min(k-x, n)$ times, 3.1 $\max(0, n-y)$ times, then 3.3.
You can try to verify that the numbers add up.
The other direction:
This is where you use structural induction.
First show $S_6$ generates $\{b^nc^k \mid n \ge k\}$.
Then show that any derivation from $S_5$ has an intermediate in $\{a^mS_6c^k \mid m \ge k\}$.
So $bS_6$ generates $\{b^nc^k \mid n > k\}$ and $S_5$ generates $\{a^mb^nc^k \mid m + n \ge k\}$.
Hence, $aS_5$ generates $\{a^mb^nc^k \mid m > 0, m + n > k\}$.
Conclude that $S_4$ generates $\{a^mb^nc^k \mid m+n > k\}$.