Kompleksitas persimpangan bahasa biasa sebagai tata bahasa bebas konteks

Diberikan reguler , apakah ada batasan non-sepele pada ukuran tata bahasa bebas konteks terkecil untuk ?R 1 ∩ ⋯ ∩ R $R_1, \dots, R_n$$R_1 \cap \cdots \cap R_n$

Ini adalah pertanyaan yang bagus dan benar-benar terletak pada minat saya. Saya senang Anda menanyakannya, Max.

Biarkan DFA dengan paling banyak menyatakan masing-masing diberikan. Akan lebih baik jika ada PDA dengan banyak negara sub-eksponensial yang menerima persimpangan bahasa DFA. Namun, saya menyarankan bahwa PDA seperti itu mungkin tidak selalu ada.O ( n $n$$O(n)$

Pertimbangkan bahasa salin. Sekarang, batasi untuk menyalin string dengan panjang n.

Secara formal, pertimbangkan copy .: = { x $n$$:=$ $\{ xx \, | \, x \in \{0,1\}^{n}\}$

Kita dapat merepresentasikan copy sebagai persimpangan DFA dengan ukuran paling banyak . Namun, DFA terkecil yang menerima -copy memiliki status.n O ( n ) n 2 Ω ( n $n$$n$$O(n)$$n$$2^{\Omega(n)}$

Demikian pula, jika kita membatasi diri pada alfabet tumpukan biner, maka saya curiga bahwa PDA terkecil yang menerima copy memiliki banyak keadaan secara eksponensial.$n$

PS Jangan ragu untuk mengirim saya email jika Anda ingin membahas lebih lanjut. :)

Saya tidak berpikir bahwa ada batas bawah atau atas non-sepele.
Untuk batas bawah, pertimbangkan bahasa untuk tetap . Ukuran tata bahasa bebas konteks terkecil adalah logaritmik dalam ukuran ekspresi reguler , sedangkan ukuran otomat terkecil untuk adalah linier dalam ukuran regex . Perbedaan eksponensial ini tetap sama jika kami memotong dengan bahasa lain seperti itu. Untuk batas atas, pertimbangkan bahasa yang terdiri dari tepat satu deBruijn-Urutan panjang . Diketahui bahwa ukuran tata bahasa terkecil untuk$L_1 = \{ a^{2^k} \}$$k$$L_1$$L_1$$L_1$$L_1$
$L_2$$n$$L_2$ adalah yang terburuk, yaitu , jadi perbedaan dengan otomat "terkecil" untuk hanyalah faktor logaritma, proposisi 1 dalam$O\left( \frac{n}{\log n} \right)$$L_2$

• D. Hucke, M. Lohrey, E. Noeth Membangun Tata Bahasa Pohon Kecil dan Sirkuit Kecil untuk Rumus , untuk muncul di FSTTCS 2014

Batas bawah atau batas atas non-trivial umum akan bertentangan dengan hasil tersebut, karena apa yang benar untuk persimpangan bahasa harus benar untuk persimpangan bahasa.$n$$1$

Biarkan saya yang kedua penilaian Michael, ini memang pertanyaan yang menarik. Gagasan utama Michael dapat dikombinasikan dengan hasil dari literatur, sehingga memberikan batas bawah yang sama dengan bukti yang kuat.

Saya akan merujuk batasan pada ukuran CFG dalam hal jumlah total simbol alfabet dalam ekspresi reguler. Biarkan nomor ini dilambangkan dengan k . (Seperti yang dicatat john_leo, kami tidak akan menemukan batasan yang berguna dalam hal jumlah ekspresi reguler yang mengambil bagian dalam persimpangan.)$n$$k$

Baik OP maupun Michael tidak merasa perlu untuk menyebutkan ini, tapi batas atas (jumlah negara) untuk mengkonversi sebuah persimpangan dari ekspresi reguler menjadi NFA dapat dengan mudah dibuktikan. Sebagai catatan, ini dia: Konversi ekspresi reguler ke Glushkov automata, yang semuanya tidak dapat dikembalikan. Kemudian terapkan konstruksi produk untuk mendapatkan NFA untuk persimpangan bahasa-bahasa ini. (Saya kira bahwa seseorang dapat meningkatkan terikat untuk 2 k + 1 atau lebih.) Sebuah s NFA -state dapat dikonversi menjadi tata bahasa yang benar-linear (yang merupakan kasus khusus dari CFG a) ukuran O ( s 2$2^{k+1}$$2^k+1$$s$$O(s^2)$(jika kita mengukur ukuran tata bahasa sebagai jumlah total simbol di sisi kiri dan kanan produksi), maka memberikan ukuran . Batas ini tentu saja terdengar mengerikan jika Anda memiliki aplikasi praktis dalam pikiran. Mencoba untuk membuktikan ikatan yang lebih baik menggunakan kompleksitas transisi nondeterministic daripada kompleksitas state nondeterministic untuk memperkirakan ukuran NFA mungkin sepadan dengan usaha.$O(4^{k})$

Bagian lainnya adalah menemukan bahasa saksi yang dapat secara ringkas diekspresikan sebagai persimpangan ekspresi reguler, tetapi tentu tidak praktis untuk dijelaskan dengan CFG. (Di sini kita perlu membuat batasan yang lebih rendah pada ukuran semua CFG yang menghasilkan bahasa, yang jumlahnya bisa sangat banyak.) Argumen berikut memberikan batas bawah.$2^{\Omega(\sqrt{k}/\log k)}$

Pertimbangkan bahasa terbatas , di mana w R menunjukkan pembalikan dari w . Kemudian L n dapat diekspresikan sebagai persimpangan dari 2 n + 1 ekspresi reguler berikut:$L_n = \{\,ww^Rw \in \{a,b\}^*\mid |w|=n\,\}$$w^R$$w$$L_n$$2n+1$

• , untuk 1 $r_i = (a+b)^ia(a+b)^{2(n-i-1)}a(a+b)^*+(a+b)^ib(a+b)^{2(n-i-1)}b(a+b)^*$ ;$1\le i \le n$
• , untuk 1 $s_i = (a+b)^*a(a+b)^{2(n-i-1)}a(a+b)^i+(a+b)^*b(a+b)^{2(n-i-1)}b(a+b)^i$ ;$1\le i \le n$
• $\ell = (a+b)^{3n}$

Jumlah total simbol alfabet di persimpangan ekspresi ini adalah dalam O ( n 2 ) .$k$$O(n^2)$

Menggunakan argumen yang diberikan dalam bukti Teorema 13 dalam ( 1 ), orang dapat membuktikan bahwa setiap CFG asiklik yang menghasilkan harus memiliki setidaknya 2 n / ( 2 n ) = 2 Ω ( $L_n$variabel yang berbeda, jika sisi kanan setiap aturan memiliki panjang paling banyak2. Kondisi terakhir diperlukan untuk memperdebatkan jumlah variabel, karena kita dapat menghasilkan bahasa yang terbatas dengan satu variabel. Tetapi dari perspektif ukuran tata bahasa, kondisi ini sebenarnya bukan batasan, karena kita dapat mengubah CFG menjadi bentuk ini hanya dengan ukuran linear, lihat (2). Perhatikan bahwa bahasa yang digunakan oleh Arvind et al. lebih dari alfabet ukurann, dan ini menghasilkan batasnn/(2n); tetapi argumen tersebut tetap dengan modifikasi yang jelas.$2^n/(2n) = 2^{\Omega(\sqrt{k}/\log k)}$$2$$n$$n^n/(2n)$

Namun, masih ada celah besar antara dan batas bawah yang disebutkan di atas.$O(4^n)$

Referensi:

• V. Arvind, Pushkar S. Joglekar, Srikanth Srinivasan. Sirkuit Aritmatika dan Produk Hadamard dari Polinomial , FSTTCS 2009, Vol. 4 LIPIcs, hlm. 25-36

• Lange, Martin; Leiß, Hans (2009). " Ke CNF atau tidak ke CNF? Versi Algoritma CYK yang Efisien dan Mudah Digunakan ". Informatica Didactica 8.