Czy { } nie jest kontekstowe?

Czy język { } jest bezkontekstowy?$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$

Uświadomiłem sobie, że spotkałem prawie wszystkie warianty tego pytania z różnymi warunkami dotyczącymi związku między i, j i k, ale nie tym.

Domyślam się, że nie jest pozbawiony kontekstu, ale czy masz dowód?

Lemat Ogdena powinien działać:

Dla danego wybierz i zaznacz wszystkie (i nic więcej).a i b p c k$p$$a^i b^p c^k$$b$

k b b i $i$ i są tak dobrane, że dla każdego wyboru ile „s faktycznie pompowana jest jedna pompowanie wykładnik takie, że liczba ” s jest równa i jeden, gdzie jest on równy .$k$$b$$b$$i$$k$

To jest i mają być ze zbioru .k ⋂ 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$

Jestem całkiem pewien, ale zbyt leniwy, aby formalnie udowodnić, że ten zestaw jest nieskończony.

Jeśli relacja między trzema ograniczeniami to „LUB”, wówczas językiem jest CFL. Rozwiązanie wykorzystuje fakt, że świetlówki kompaktowe są zamknięte w ramach unii. Oczywiste są następujące CFL: , , (jeśli nie jest się przekonanym, można spojrzeć na jako konkatenację CFL i zwykły język. Na przykład jest połączony z .$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\}$$L_i$$L_1${ c } $\{a^ib^j\mid i\ne j \}$$\{c\}^*$

Pożądanym językiem jest połączenie powyższego . To jest CFL.$L=L_1\cup L_2\cup L_3$