Mungkinkah ada lemma pemompa konteks-sensitif?

8

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)?

lukas.coenig
sumber
2
Bisakah Anda memberikan definisi formal tentang "memompa lemma"? Jika tidak, tidak ada bukti seperti itu secara prinsip.
Raphael
Mungkin orang dapat membantah teorema Parikh untuk bahasa-bahasa yang peka terhadap konteks, dan ini membuat kita berharap bahwa tidak ada lemma yang memompa menyerupai yang kita ketahui ada.
Yuval Filmus
@YuvalFilmus Apa maksudmu? Jelas bilangan prima peka konteks, dan tidak semilinear. Jadi Parikh tidak berlaku untuk konteks sensitif. Itu berarti bahwa "pemompaan linier" tidak berlaku. Seperti Raphael, saya penasaran apa metode lain yang dianggap memompa.
Hendrik Jan
1
Anda benar, karena mengetahui apa sebenarnya "pemompaan" itu ... Saya berharap untuk beberapa saran ... Apa teorema Parikh untuk bahasa yang peka konteks ? Saya hanya menemukan satu untuk bahasa bebas konteks.
lukas.coenig
1
@ lukas.coenig Tidak ada teorema Parikh untuk bahasa yang peka terhadap konteks, tetapi mungkin ada satu jika ada lemma pemompaan sederhana untuk bahasa yang peka terhadap konteks.
Yuval Filmus

Jawaban:

8

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 bahasaCmemiliki lemma pemompaan jika ada predikat terner yang dapat ditentukanP(,,) dimana P(g,w,d) cara:

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

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

Misalnya, lemma pemompaan untuk bahasa biasa akan memunculkan predikat "g mengkodekan ε-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 ituw,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Π20adalah 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Π20-lengkap.

Telah diketahui secara luas bahwa masalah tak terhingga untuk bahasa-bahasa yang berulang secara berulang adalah Π20-complete (lebih sering, seseorang menemukan rumusan bahwa masalah finiteness adalah Σ20-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

{u#vv is a shortlex-minimal accepting computation of M on input u}.
Kemudian, L(A) iff tak terbatas L(M) tidak terbatas, yang melengkapi bukti kami.

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

Georg Zetzsche
sumber