Apakah { } tidak bebas konteks?

Apakah bahasa { } bebas konteks atau tidak?$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$

Saya menyadari bahwa saya telah menemukan hampir semua varian pertanyaan ini dengan kondisi yang berbeda tentang hubungan antara i, j, dan k, tetapi tidak yang ini.

Dugaan saya adalah bahwa itu tidak bebas konteks, tetapi apakah Anda punya bukti?

Lemma Ogden seharusnya bekerja:

Untuk diberikan memilih sebuah i b p c k dan tandai semua b 's (dan tidak ada lagi).$p$$a^i b^p c^k$$b$

dan k dipilih sedemikian rupa sehingga untuk setiap pilihan berapa b sebenarnya dipompa ada satu eksponen memompa sedemikian sehingga jumlah b sama dengan i dan satu di mana sama dengan k .$i$$k$$b$$b$$i$$k$

Yaitu dan k harus dari himpunan ⋂ 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$

Saya cukup yakin tetapi terlalu malas untuk membuktikan secara resmi bahwa set ini tidak terbatas.

Jika hubungan antara ketiga batasan tersebut adalah "ATAU", bahasanya adalah CFL. Solusinya menggunakan fakta bahwa CFL ditutup di bawah serikat. Jelas, berikut ini adalah 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\}$ (jika seseorang tidak yakin, seseorang dapat melihat L i sebagai gabungan dari CFL dan bahasa reguler. Misalnya, L 1 adalah { a i b j ∣ i ≠ j } digabungkan ke { 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\}^*$

Bahasa yang diinginkan adalah penyatuan . Jadi, itu adalah CFL.$L=L_1\cup L_2\cup L_3$