Varian Masalah Korespondensi

Ini mungkin cukup sederhana, tetapi pertimbangkan Masalah Post Correspondence standar:

Mengingat dan β 1 , ... , β N , menemukan urutan indeks i 1 , ... , i K sehingga a i 1 ⋯ α i K = β i 1 ⋯ β i K . Ini, tentu saja, tidak dapat dipastikan.$\alpha_1, \ldots, \alpha_N$$\beta_1, \ldots, \beta_N$$i_1, \ldots, i_K$$\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{i_1}\cdots \beta_{i_K}$

Sekarang, saya menyebutnya 'varian', tetapi sebenarnya tidak - itu pada dasarnya membuang 'korespondensi'. Pokoknya, pertimbangkan varian berikut:

Diberikan dan β 1 , ... , β N , temukan dua urutan indeks i 1 , ... , i K , j 1 , ... , j K sedemikian rupa sehingga α i 1 ⋯ α i K = β j 1 ⋯ ß j K . Apa yang bisa dikatakan tentang varian ini? Jika ini sepele, saya minta maaf!$\alpha_1, \ldots, \alpha_N$$\beta_1, \ldots, \beta_N$$i_1, \ldots, i_K, j_1, \ldots, j_{K}$$\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{j_1}\cdots \beta_{j_{K}}$

Versi baru ini - di mana - dapat dipilih.$K = K'$

Mari kita tunjukkan bahwa bahasa adalah CFL. Kemudian decidability mengikuti dari decidability dari kekosongan CFL.$L := \bigcup_{k \geq 1} (A^k \ \cap \ B^k)$

Kami akan merancang sebuah PDA untuk menerima . Pada input x , PDA ini akan mencoba untuk membangun dua faktorisasi dari x , satu menggunakan kata-kata dari A , dan menggunakan kata-kata lain dari B . Ini akan menggunakan penghitung pada tumpukan untuk memastikan dua faktorisasi ini memiliki panjang yang sama. Secara konseptual saya akan merujuk pada A -faktorisasi x sejauh duduk di atas x dan B -factorisasi sebagai duduk di bawah x . Maka stack akan berisi n counter jika nilai absolut dari perbedaan jumlah kata yang cocok di atas, dikurangi jumlah kata di bawah, adalah$L$$x$$x$$A$$B$$A$$x$$x$$B$$x$$n$ . Kita memerlukan keadaan lain dari PDA untuk mencatat tanda yang sesuai dengan n (yang memberi tahu kita jikafaktorisasi- A lebih panjang daripada faktor- B , atau sebaliknya).$n$$n$$A$$B$

Saat kita memindai huruf , kita secara nondestinistik menebak kata t dari A dan kata u dari B yang menjadi awal surat ini. Setelah kami menebak, kami berkomitmen untuk mencocokkan sisa t dan u dengan x ; jika pada suatu saat pertandingan kami gagal, kami menghentikan pilihan nondeterministik ini. Jadi kami juga mempertahankan, dalam keadaan PDA kami, sufiks t dan u yang tetap cocok.$x$$t$$A$$u$$B$$t$$u$$x$$t$$u$

Saat kami memindai surat lebih lanjut, kami terus mencocokkan sampai kami mencapai akhir atau akhir u (atau keduanya). Ketika kami mencapai akhir kata, kami memperbarui tumpukan dengan tepat, dan kemudian menebak kata baru yang cocok di bagian atas atau bawah (atau keduanya).$t$$u$

Kami menerima jika sufiks yang tersisa untuk dicocokkan keduanya kosong di atas dan bawah, dan tumpukan tidak mengandung penghitung.

Kami dapat membuat PDA ini secara efektif, sehingga kami dapat memutuskan secara efektif apakah ia menerima sesuatu atau tidak (misalnya, dengan mengkonversi secara efektif ke tata bahasa dan kemudian menggunakan metode yang biasa untuk melihat apakah G menghasilkan sesuatu).$G$

$k$$2^{O(l^2)}$$l$$A$$B$

$A$$B$$A$$B$

$\alpha_{i_1} \cdots \alpha_{i_K} = \beta_{j_1} \cdots \beta_{j_{K'}}$$K = K'$

$A$$\alpha_{i_1} \cdots \alpha_{i_K}$$B$$\beta_{j_1} \cdots \beta_{j_{K'}}$$A \cap B$$A,B$