Find CFG for $a^i b^j c^k$ with $!(i=j=k)$

Question

I need to show that the following language is context free: It contains all words $a^i b^j c^k$ with the condition that there're not exactly as many a's and b's and c's.

I would write it like this: $$\{a^i b^j c^k\; : \;\;!(i=j=k) \;\}$$

Here's what I've come up with:

I split it up into four cases. In three cases two are equal. In the fourth case they're all distinct.

1. $i=j \neq k: \{a^i b^j c^k : \;i=j \lt k \;\} \cup \{a^i b^j c^k : \;i=j \gt k \;\}$
2. $i=k \neq j: \{a^i b^j c^k : \;i=k \lt j \;\} \cup \{a^i b^j c^k : \;i=k \gt j \;\}$
3. $j=k \neq i: \{a^i b^j c^k : \;j=k \lt i \;\} \cup \{a^i b^j c^k : \;j=k \gt i \;\}$
4. $i \neq j \neq k: \{a^i b^j c^k : i \lt j \lt k \;\} \cup \{a^i b^j c^k : j \lt i \lt k \;\} \cup \{a^i b^j c^k : k \lt i \lt j \;\} \cup \{a^i b^j c^k : k \lt j \lt i \;\}$

I'm not quite sure about the last cause, though.

I do understand how to create a CFG for conditions like $k=i+j$, $(i=j) \lor (j=k)$. But I can't figure out how to create a CFG for these sub-languages.

Any help would be appreciated!

Answer 1

First note that $ \neg(i=j$ and $j=k)$ is $(i \neq j $ or $j \neq k ) $ (Demorgan's Law)

$S \to S_1|S_2 \\ S_1 \to XC \\X \to aA|bB|aXb \\S_2\to AY\\ Y\to bYc|bB|cC\\ A\to aA|\epsilon\\ B\to bB|\epsilon\\ C\to cC|\epsilon$

Answer 2

S -> S1 C | S2 C | A S3 | A S4

S1 , #of a's greater than # of b's

S2 , # of a's lesser than # of b's

S3 , # of b's greater than # of c's

S4 , # of b's lesser than # of c's

S -> S1 C | S2 C | A S3 | A S4

S1 -> aA | a S1 b

S2 -> bB | a S2 b

S3 -> bB | b S3 c

S4 -> cC | b S4 c

A -> aA | E

B -> bB | E

C -> cC | E