Est-ce que {

La langue est-elle { } hors contexte ou non?$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$

J'ai réalisé que j'ai rencontré presque toutes les variantes de cette question avec des conditions différentes sur la relation entre i, j et k, mais pas celle-ci.

Je suppose que ce n'est pas sans contexte, mais avez-vous une preuve?

Le lemme d'Ogden devrait fonctionner:

Pour un donné, choisissez a i b p c k et marquez tous les b (et rien d'autre).$p$$a^i b^p c^k$$b$

et k sont choisis de telle sorte que pour chaque choix du nombre de b réellement pompés, il y ait un exposant de pompage tel que le nombre de b soit égal à i et un où il est égal à k .$i$$k$$b$$b$$i$$k$

C'est-à-dire que et k doivent provenir de l'ensemble ⋂ 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$

Je suis bien sûr mais trop paresseux pour prouver formellement que cet ensemble est infini.

Si la relation entre les trois restrictions est "OU", alors la langue est CFL. La solution utilise le fait que les LFC sont fermées sous l'union. De toute évidence, les CFL sont les suivants: , 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 l'on n'est pas convaincu, on peut considérer L i comme une concaténation de CFL et du langage régulier. Par exemple, L 1 est { a i b j ∣ i ≠ j } concaténé à { 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\}^*$

La langue souhaitée est l'union de ci-dessus . C'est donc CFL.$L=L_1\cup L_2\cup L_3$