Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
