É {

É o idioma { } ou não livre de contexto?$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$

Percebi que encontrei quase todas as variantes dessa questão com diferentes condições sobre a relação entre i, j e k, mas não essa.

Meu palpite é que não é livre de contexto, mas você tem uma prova?

O lema de Ogden deve funcionar:

Para um dado escolha a i b p c $p$$a^i b^p c^k$ e marque todos os (e nada mais).$b$

e k são escolhidos de tal forma que, para cada escolha de quantos b 's são realmente bombeados, existe um expoente de bombeamento tal que o número de b ' s seja igual a$i$$k$$b$$b$ um onde seja igual a k .$i$$k$

Ou seja, e k devem ser do conjunto ⋂ 1 ≤ n ≤ p { p - n + m ∗ n ∣ m ∈ N 0 } .$i$$k$$\bigcap_{1 \leq n \leq p} \lbrace p-n + m*n \mid m \in \mathbb{N}_0\rbrace$

Tenho certeza, mas com preguiça de provar formalmente que esse conjunto é infinito.

Se a relação entre as três restrições for "OR", o idioma será CFL. A solução usa o fato de que as CFLs estão fechadas em união. Claramente, os seguintes são CFLs: , L 2 = { a i b j c k ∣ i ≠ k , j ≥ 0 } , L 3 = { a i $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\}$ (se não se convencer, pode-se considerar L i como concatenação de CFL e linguagem regular. Por exemplo, L 1 é { a i b j ∣ i ≠ j } concatenado para { c } ∗ .$L_3=\{a^ib^jc^k \mid j\ne k,\ i\ge 0\}$$L_i$$L_1$$\{a^ib^j\mid i\ne j \}$$\{c\}^*$

O idioma desejado é a união do anterior . Então, é CFL.$L=L_1\cup L_2\cup L_3$