Construct the CFG for the complement of $$L = \{ a^ib^jc^k \mid i \ge 0, j \ge 0, k \ge 0 \text{ and } i \ge j + k \}$$
I tried to write the complement as the union of $L = \{ a^ib^jc^k \mid i \ge 0, j \ge 0, k \ge 0 \text{ and } i < j + k \}$ and $\{0,1,2\}^* \setminus 0^*1^*2^*$
But it's a bit hard for me to construct the CFG for this sets.
any help please?
Here are the productions of a context-free grammar that generates
$$L'=\left\{a^ib^jc^k:i,j,k\ge 0\text{ and }i<j+k\right\}\,.$$
$$\begin{align*} S&\to C_0\\ C_0&\to aC_0c\mid C_1c\mid Bb\\ C_1&\to aC_1c\mid C_1c\mid B\\ B&\to aBb\mid Bb\mid\epsilon \end{align*}\tag{1}$$
$C_0$ generates strings of the forms $\color{red}{a^nBbc^n}$ and $a^nC_1c^{n+1}$ for $n\ge 0$. In the latter case the $C_1$ productions eventually yield a string of the form $\color{blue}{a^nBc^m}$ for some $n\ge 0$ and $m>n$. $B$ then generates words of the form $a^kb^\ell$, where $0\le k\le\ell$, so that we end up with a word of the form $\color{red}{a^{n+k}b^{\ell+1}c^n}$, where $n\ge 0$ and $0\le k\le\ell$, or a word of the form $\color{blue}{a^{n+k}b^\ell c^m}$, where $0\le n<m$ and $0\le k\le\ell$. In the first case $n+k<\ell+1+n$, and in the second case $n+k<\ell+m$, so all of these words are in $L'$, and it’s not hard to see that every word in $L'$ is generated by this grammar.
Every word in $\{a,b,c\}^*$ that is not of the form $a^ib^jc^k$ contains one of the sequences $ba$, $ca$, and $cb$, so this part of the complement of $L$ can even be generated by a simple regular grammar; I’ll leave it to you to design such a grammar. Say that it’s initial symbol is $T$; then to finish the job you need only add the productions of that grammar (assuming that they does not use any of the non-terminal symbols $S,C_0,C_1$, and $B$, of course!) and a production $S\to T$ to $(1)$.
