CFG for $\{a^ib^jc^k \mid i \neq j+k\}$

Question

I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq j+k\}$ over the alphabet $\Sigma = \{a,b,c\}$.

I know that I can split this up into the union of two cfg's $S_1$ and $S_2$,
where $S_1$ is the case where $\#_a \lt \#_b + \#_c$,
and $S_2$ is the case where $\#_a \gt \#_b + \#_c$.

I keep producing the grammar that generates this language but not in the correct order, that is I am having a hard time keeping the $a$'s on the left, $b$'s in the middle, and $c$'s to the right. Is this even context free?

Answer 1

I would start by finding a CFG that generates the balanced version $\{a^ib^jc^k\mid i=j+k\}$ from nonterminal $C$.

$C\rightarrow aCc\mid B \\ B\rightarrow aBb\mid\varepsilon$

Now, as you correctly note, there are two possibilities on how to get the unbalanced version; either there is $(a^+)$ to the left, or $(b^+\mid b^*c^+)$ on the right. To deal with the former possibility, you simply add the following rules.

$ S\rightarrow aL\\ L\rightarrow aL\mid C $

You can deal with the other two possibilities in similar manner.

$ S\rightarrow R_bb\mid R_cc\\R_c\rightarrow R_cc\mid R_b\mid C\\R_b\rightarrow R_bb\mid B$

Answer 2

The split you made is actually a good design decision.

The language is context-free. Keep a central non-terminal, write $a$'s to the left, and $b,c$'s to the right. If you generate the $c$'s before you generate the $b$'s all letters stay in alphabetic order.