Es {

¿El lenguaje { } está libre de contexto o no?$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$

Me di cuenta de que he encontrado casi todas las variantes de esta pregunta con diferentes condiciones sobre la relación entre i, j y k, pero no esta.

Supongo que no está libre de contexto, pero ¿tienes una prueba?

El lema de Ogden debería funcionar:

Para una dada, elija a i b p c k y marque todas las b '(y nada más).$p$$a^i b^p c^k$$b$

y k se eligen de tal manera que para cada elección de cuántas b 's se bombean realmente hay un exponente de bombeo tal que el número de b es igual a i y uno donde es igual a k .$i$$k$$b$$b$$i$$k$

Es decir, y k deben ser del 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$

Estoy bastante seguro pero demasiado vago para demostrar formalmente que este conjunto es infinito.

Si la relación entre las tres restricciones es "O", entonces el idioma es CFL. La solución utiliza el hecho de que las CFL están cerradas bajo unión. Claramente, los siguientes son CFL: , 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\}$ (si uno no está convencido, uno puede ver a L i como concatenación de CFL y lenguaje regular. Por ejemplo, L 1 es { a i b j ∣ i ≠ j } concatenado a { 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\}^*$

El lenguaje deseado es la unión de lo anterior . Entonces, es CFL.$L=L_1\cup L_2\cup L_3$