<p>If the relation between the three restrictions is "OR", then the language is CFL.
The solution uses the fact that CFLs are closed under union.
Clearly, the following are CFLs:
$L_1=\{a^ib^jc^k \mid i\ne j,\ k\ge 0\}$, 
$L_2=\{a^ib^jc^k \mid i\ne k,\ j\ge 0\}$,
$L_3=\{a^ib^jc^k \mid j\ne k,\ i\ge 0\}$
(if one is not convinced, one can look on $L_i$ as concatenation of CFL and regular language. For instance, $L_1$ is $\{a^ib^j\mid i\ne j \}$ concatenated to $\{c\}^*$.</p>

<p>The desired language is the union of the above $L=L_1\cup L_2\cup L_3$.
So, it is CFL.</p>

CC BY-SA 3.0
2011-05-26T07:45:45.340Z
This is wrong. For example, $aabcc\in L_1$ and hence in your $L$, but $aabcc\notin\lbrace a^ib^jc^k~|~i\neq j,i\neq k,j\neq k\rbrace$.
Dave Clarke
CC BY-SA 3.0
2011-05-26T14:49:06.713Z
You assume that »the relation between the three restrictions is "OR"«, but this is not the intended meaning. All of the restrictions have to hold (cf. Dave Clarke's counterexample), and then the language is not context-free (cf. the answer above).
DaniCL
CC BY-SA 3.0
2011-05-26T07:33:30.150Z
2011-05-26T07:33:30.150Z
R_G
<p>Ogden's lemma should work:</p>

<p>For a given $p$ choose $a^i b^p c^k$ and mark all the $b$'s (and nothing else).</p>

<p>$i$ and $k$ are chosen such that for every choice of how many $b$'s are actually pumped there is one pumping exponent such that the number of $b$'s is equal to $i$ and one where it is equal to $k$.</p>

<p>That is $i$ and $k$ have to be from the set $\bigcap_{1 \leq n \leq p} \lbrace p-n + m*n \mid m \in \mathbb{N}_0\rbrace$.</p>

<p>I am quite sure but too lazy to formally prove that this set is infinite.</p>

CC BY-SA 3.0
2011-10-27T12:05:55.183Z
This answer is [featured on the community blog](http://is.gd/hhTZfI).
Aaron Sterling
CC BY-SA 3.0
2014-01-02T18:44:12.813Z
A similar proof is presented in [this answer](http://cs.stackexchange.com/a/279/199) on cs.se.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-01T00:28:28.633Z
Assuming that IN_0 means the set of nonnegative integers, the mentioned set is infinite because it contains p+im for i=0, 1, 2, …, where m is the least common multiple of {1, …, p}.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T00:32:28.297Z
Those who did not know Ogden’s lemma (like me) may find [Wikipedia](http://en.wikipedia.org/wiki/Ogden%27s_lemma) helpful.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T06:30:08.323Z
@Tsuyoshi: Yes, you're right. I didn't see this simple representation yesterday night.
Frank Weinberg
CC BY-SA 3.0
2010-09-30T21:37:49.653Z
2011-09-20T20:06:21.443Z
2011-09-20T20:06:21.443Z
Frank Weinberg
<p>Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not? </p>

<p>I realized that I have encountered almost all variants of this question with different conditions about the relationship between i, j, and k, but not this one.</p>

<p>My guess is that it is not context-free, but do you have a proof?</p>

CC BY-SA 3.0
2011-09-24T07:41:28.067Z
Curiously, this language (and the use of Ogden's Lemma) can be found in Example 6.3 (p. 130) in the classical version of Hopcroft and Ullman's "Introduction to Automata Theory, Languages and Computation".
Dominik D. Freydenberger
CC BY-SA 2.5
2010-09-30T19:30:15.860Z
Seems like a homework problem.
Sariel Har-Peled
CC BY-SA 2.5
2010-09-30T19:57:13.893Z
@Sariel: I hope that it is not a homework problem, because I do not know how to solve it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-30T19:58:46.030Z
It looks like a homework problem, since some of the other variants that I mention are sufficiently easy to be homework problems. But this variant is not a homework problem. I would be glad if anyone can give me a link to any course site where this particular problem has been assigned as a homework, though.
Cem Say
CC BY-SA 2.5
2010-09-30T23:01:51.870Z
Can you explain why the standard techniques don't work?
Warren Schudy
CC BY-SA 2.5
2010-10-01T00:46:27.613Z
@Tsuyoshi... Yeh. You are right. Its harder than it looks.
Sariel Har-Peled
<automata-theory><fl.formal-languages><grammars>
Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?
Cem Say
# Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?

(Asked by: username_0 on 2010-09-30)

Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not?

I realized that I have encountered almost all variants of this question with different conditions about the relationship between i, j, and k, but not this one.

My guess is that it is not context-free, but do you have a proof?

**Tags:** automata-theory, fl.formal-languages, grammars

> **Comments:**
> **username_2**: Seems like a homework problem.  
> **username_3**: @Sariel: I hope that it is not a homework problem, because I do not know how to solve it.  
> **username_0**: It looks like a homework problem, since some of the other variants that I mention are sufficiently easy to be homework problems. But this variant is not a homework problem. I would be glad if anyone can give me a link to any course site where this particular problem has been assigned as a homework, though.  
> **username_4**: Can you explain why the standard techniques don't work?  
> **username_2**: @Tsuyoshi... Yeh. You are right. Its harder than it looks.  
> **username_1**: Curiously, this language (and the use of Ogden's Lemma) can be found in Example 6.3 (p. 130) in the classical version of Hopcroft and Ullman's "Introduction to Automata Theory, Languages and Computation".  

---

## 2 answers

### Answer by username_8 on 2010-09-30. Score: 29 | Accepted answer

Ogden's lemma should work:

For a given $p$ choose $a^i b^p c^k$ and mark all the $b$'s (and nothing else).

$i$ and $k$ are chosen such that for every choice of how many $b$'s are actually pumped there is one pumping exponent such that the number of $b$'s is equal to $i$ and one where it is equal to $k$.

That is $i$ and $k$ have to be from the set $\bigcap\_{1 \leq n \leq p} \lbrace p-n + m\*n \mid m \in \mathbb{N}\_0\rbrace$.

I am quite sure but too lazy to formally prove that this set is infinite.

> **Comments:**
> **username_3**: Assuming that IN_0 means the set of nonnegative integers, the mentioned set is infinite because it contains p+im for i=0, 1, 2, …, where m is the least common multiple of {1, …, p}.  
> **username_3**: Those who did not know Ogden’s lemma (like me) may find [Wikipedia](http://en.wikipedia.org/wiki/Ogden%27s_lemma) helpful.  
> **username_8**: @Tsuyoshi: Yes, you're right. I didn't see this simple representation yesterday night.  
> **username_9**: This answer is [featured on the community blog](http://is.gd/hhTZfI).  
> **username_10**: A similar proof is presented in [this answer](http://cs.stackexchange.com/a/279/199) on cs.se.  

---

### Answer by username_5 on 2011-05-26. Score: -4

If the relation between the three restrictions is "OR", then the language is CFL.
The solution uses the fact that CFLs are closed under union.
Clearly, the following are CFLs:
$L\_1=\{a^ib^jc^k \mid i\ne j,\ k\ge 0\}$,
$L\_2=\{a^ib^jc^k \mid i\ne k,\ j\ge 0\}$,
$L\_3=\{a^ib^jc^k \mid j\ne k,\ i\ge 0\}$
(if one is not convinced, one can look on $L\_i$ as concatenation of CFL and regular language. For instance, $L\_1$ is $\{a^ib^j\mid i\ne j \}$ concatenated to $\{c\}^\*$.

The desired language is the union of the above $L=L\_1\cup L\_2\cup L\_3$.
So, it is CFL.

> **Comments:**
> **username_6**: This is wrong. For example, $aabcc\in L_1$ and hence in your $L$, but $aabcc\notin\lbrace a^ib^jc^k~|~i\neq j,i\neq k,j\neq k\rbrace$.  
> **username_7**: You assume that »the relation between the three restrictions is "OR"«, but this is not the intended meaning. All of the restrictions have to hold (cf. username_6's counterexample), and then the language is not context-free (cf. the answer above).  

---

