Mungkinkah ada lemma pemompa konteks-sensitif?

Properti "memompa" (kata-kata dengan panjang tertentu menyiratkan keberadaan loop dalam mekanisme pendefinisian bahasa) diketahui ada untuk bahasa reguler dan bebas konteks dan beberapa lainnya (biasanya digunakan untuk menyangkal keanggotaan bahasa ke kelas tertentu) ).

Dalam diskusi seputar pertanyaan ini , jawaban Daisy menunjukkan bahwa tidak ada lemma yang memompa untuk bahasa yang peka terhadap konteks - karena mereka begitu kompleks.

Apakah itu benar - dapatkah ditunjukkan bahwa tidak ada jenis properti pemompaan - dan adakah referensi yang bagus untuk itu (atau menentangnya)?

Berikut adalah beberapa bukti bahwa tidak ada lemma yang memompa untuk bahasa yang peka konteks.

Tentu saja, sebuah jawaban bergantung pada pertanyaan apa itu lemma yang memompa. Definisi masuk akal terlemah yang dapat saya pikirkan adalah ini: Kelas bahasa$\mathcal{C}$memiliki lemma pemompaan jika ada predikat terner yang dapat ditentukan$P(\cdot,\cdot,\cdot)$ dimana $P(g,w,d)$ cara:

• $g$ adalah kata yang mengkode bahasa $L(g)$ dari $\mathcal{C}$ (pikirkan: tata bahasa),
• $w$ adalah kata dalam bahasa yang disandikan oleh $g$
• $d$adalah kata yang menyandikan perhitungan / derivasi yang dapat dipompa untuk$w$(pikirkan: perhitungan NFA dengan status berulang atau pohon derivasi CFG dengan nonterminal berulang). Di sini, pumpable artinya: ada banyak kata dalam$L(g)$.

Selain itu, kami ingin yang diberi bahasa $L$ di $\mathcal{C}$ dikodekan oleh $g$, untuk setiap kata yang cukup panjang $w\in L$, ada sebuah kata $d$ seperti yang $P(g,w,d)$.

Misalnya, lemma pemompaan untuk bahasa biasa akan memunculkan predikat "$g$ mengkodekan $\varepsilon$-NFA gratis dan $d$ menyandikan proses yang mengulangi status dan membaca $w$". Untuk penyandian yang sesuai, ini jelas memenuhi persyaratan di atas.

Sekarang, mari kita tunjukkan bahwa predikat semacam itu tidak ada untuk bahasa yang peka konteks.

Amati bahwa jika kelas bahasa memiliki lemma pemompaan, maka masalah infinity (Diberi tata bahasa, apakah itu menghasilkan bahasa yang tak terbatas?) Secara berulang dihitung: Diberikan pengkodean $g$, kita dapat menyebutkan kata-kata $w$ dan $d$ dan periksa apakah $P(g,w,d)$. Jika kami menemukan itu$w,d$, kami menjawab 'ya', jika tidak, kami melanjutkan enumerasi.

Namun, kami menunjukkan bahwa masalah infinity untuk bahasa yang peka konteks tidak dapat dihitung secara rekursif. Ingat itu$\Pi_2^0$adalah tingkat hirarki aritmatika yang secara ketat menyertakan bahasa yang berulang secara berulang. Karenanya, cukup untuk membuktikan:

Klaim : Masalah tak terhingga untuk bahasa yang peka konteks adalah$\Pi_2^0$-lengkap.

Telah diketahui secara luas bahwa masalah tak terhingga untuk bahasa-bahasa yang berulang secara berulang adalah $\Pi_2^0$-complete (lebih sering, seseorang menemukan rumusan bahwa masalah finiteness adalah $\Sigma_2^0$-lengkap). Oleh karena itu, cukup untuk mengurangi masalah yang terakhir menjadi masalah tanpa batas untuk bahasa yang peka konteks.

Diberi TM $M$, kami membuat LBA $A$ untuk bahasa

Pembaruan: Mencoba lebih jelas. Pembaruan: Contoh yang ditambahkan.