Apakah ada masalah terbuka yang tersisa tentang DFA?

Setelah mempelajari deterministic finite state automata (DFA) di tingkat sarjana, saya merasa mereka sangat dipahami. Pertanyaan saya adalah apakah ada sesuatu yang masih belum kita mengerti tentang mereka. Maksud saya bukan generalisasi DFA tetapi DFA asli yang tidak dimodifikasi yang kami pelajari di tingkat sarjana.

Ini adalah pertanyaan yang tidak jelas tetapi saya harap Anda mendapatkan idenya. Saya ingin memahami apakah adil untuk mengatakan bahwa kami sepenuhnya memahami DFA. Jadi saya benar-benar bermaksud pertanyaan yang secara inheren tentang DFA, bukan masalah yang dibuat secara buatan agar terlihat seperti masalah tentang DFA. Biarkan saya memberi contoh masalah seperti itu. Misalkan L menjadi bahasa kosong jika P = NP dan beberapa bahasa tidak tetap tetap jika P bukan NP. Bisakah L diterima oleh DFA? Pertanyaan ini tentang DFA, tetapi ini bukan tentang mereka secara rohani. Saya harap poin saya jelas dan saya tidak mendapatkan jawaban yang tidak masuk akal dari orang-orang.

Singkatnya apakah itu adil untuk dikatakan

Kami pada dasarnya sepenuhnya memahami DFA.

Saya menyesal jika ternyata ini adalah bidang penelitian besar yang tidak saya sadari dan saya baru saja menghina seluruh masyarakat.

Berikut adalah satu masalah yang dijelaskan dalam buku "Kursus kedua dalam bahasa formal dan teori automata" oleh Shallit.

Biarkan dan menjadi dua kata berbeda dengan . Berapa ukuran DFA terkecil yang menerima tetapi menolak , atau sebaliknya?v | kamu | = | v | = N u $u$$v$$|u|=|v|=n$$u$$v$

Robson, dalam makalahnya " Memisahkan string dengan automata kecil " pada tahun 1989 membuktikan batas atas . Batas bawah paling dikenal di .Ω ( log n $O(n^{2/5}(\log n)^{3/5})$$\Omega(\log n)$

Untuk survei lihat ini .

Inilah masalah keputusan yang sangat sederhana tentang DFA. Dengan DFA M, apakah M menerima representasi basis-2 dari setidaknya satu bilangan prima?

Saat ini, kami bahkan tidak tahu apakah masalah ini dapat dipecahkan secara rekursif.

Jika dipecahkan secara rekursif, dan kami memiliki algoritme untuknya, kami dapat menyelesaikan masalah terbuka yang sudah lama ada tentang apakah ada bilangan prima Fermat (bilangan prima dari bentuk ) lebih besar dari yang diketahui terbesar, 65537. (Karena prime mana pun dengan basis-2 representasi dari bentuk harus menjadi perdana Fermat.)1 0 +$2^{2^n} + 1$$1 0^+ 1$

Dugaan Černý masih terbuka dan penting. Ini adalah tentang DFA yang memiliki kata sinkronisasi (kata dengan properti yang dua salinan automaton dimulai di negara yang berbeda selalu berakhir dalam keadaan yang sama satu sama lain setelah keduanya memproses kata), dan bertanya apakah (untuk status) automata) panjang kata terpendek seperti itu selalu paling banyak . Batas terbukti terbaik adalah dari bentuk .( n - 1 ) 2 O ( n 3$n$$(n-1)^2$$O(n^3)$

Saya ingin menunjukkan masalah penelitian lain, yang menyangkut interaksi konsep yang sangat mendasar tentang DFA.

Telah diketahui secara umum bahwa setiap NFA keadaan-n dapat dikonversikan menjadi suatu DFA ekivalen yang memiliki paling banyak keadaan. Ini adalah yang terbaik dalam kasus terburuk, dalam arti bahwa ada bahasa reguler dari kompleksitas keadaan nondeterministik n (yaitu, jumlah negara dalam NFA minimal), tetapi kompleksitas keadaan deterministik . Ada juga contoh keluarga bahasa, di mana nondeterminisme dapat menyelamatkan faktor kuadrat, dan kasus-kasus di mana nondeterminisme tidak membantu menyelamatkan negara sama sekali. Jadi pertanyaan alami adalah sebagai berikut:2 $2^n$$2^n$

Masalah angka ajaib

Apakah di sana, untuk setiap antara dan , bahasa biasa sehingga kesenjangan antara kompleksitas keadaan nondeterministik dan kompleksitas keadaan deterministik persis ?n 2 n L n$\alpha$$n$$2^n$$L_n$$\alpha$

Jika kita benar-benar memahami konstruksi powerset dan relasi Myhill-Nerode dari perspektif matematika, maka saya akan berharap seseorang dapat membangun bahasa seperti itu untuk setiap , atau sebagai alternatif untuk menentukan nilai yang tidak mungkin dilakukan. (jika nilai-nilai tersebut ada, ini disebut sebagai "angka ajaib").$\alpha$$\alpha$

Diketahui bahwa ada angka ajaib untuk input ukuran alfabet , dan, sejak 2009, bahwa tidak ada angka ajaib jika ukuran alfabet setidaknya . Tetapi jika saya tidak salah, kasus huruf biner masih terbuka.$1$$3$

Galina Jirásková. Angka ajaib dan alfabet terner. Dalam: Konferensi Internasional ke-13 tentang Perkembangan Teori Bahasa (DLT 2009), volume 5583 Catatan Kuliah di Ilmu Komputer, halaman 300–311.

Judul: Persimpangan non-kekosongan untuk dua DFA

Keterangan: Mengingat dua DFA ini dan D 2 , tidak terdapat string x sehingga D 1 dan D 2 keduanya menerima x ?$D_1$$D_2$$x$$D_1$$D_2$$x$

Terbuka Soal: Bisakah kita memecahkan persimpangan non-kekosongan untuk dua di DFA ini waktu?$o(n^2)$

Jika kita dapat memecahkan masalah ini dalam waktu mana δ <2, maka hipotesis waktu eksponensial yang kuat akan ditolak.$O(n^{\delta})$$\delta$

Penjelasan: Memutuskan kekosongan persimpangan bahasa-bahasa reguler dalam waktu subquadratic

Anda mungkin menemukan ini membantu: http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Semoga hari mu menyenangkan! :)

Berikut ini adalah masalah terbuka yang berkaitan dengan DFA dan teori pembelajaran mesin: apakah acak seragam (transisi acak dan perilaku terima / tolak) yang dipelajari DFA dalam model PAC?

Catatan: kami pikir DFA sewenang-wenang tidak dapat dipelajari b / c dari hasil kekerasan kriptografi . Untuk DFA acak, kami hanya memiliki batas bawah SQ , yang tidak sekuat.

$L$$L$$L$$l$$L$$l$$L$$l$$O(n^2)$

$n$

Sepertinya saya bahwa formula bentuk tertutup harus ada, tetapi tidak ada yang diketahui. Beberapa batas asimptotik diketahui:

$n$

Berikut adalah pertanyaan terkait DFA yang pernah saya kunjungi sebelumnya, dan masih terbuka sejauh yang saya tahu:

$n$$\Sigma=\{0,1\}$$DFA(n)$$n$$|DFA(n)| = n^{2n}2^n$

$x,y\in\Sigma^*$$K_n(x,y)$$DFA(n)$ $x$$y$

$K_n(x,y)$$K_n(x,y)$$poly(n,|x|,|y|)$

Pertanyaan ini memiliki implikasi untuk pembelajaran mesin .

("Berpikir di luar kotak" ...) ini adalah masalah yang agak rumit yang melibatkan DFA (belum melihatnya dipelajari di tempat lain) tetapi memanifestasikan tema dalam TCS yang bahkan banyak objek komputasi yang tampaknya "sederhana" (seperti DFA) dapat memiliki sifat kompleks , juga aspek / tema yang terkandung dalam teorema Rices. (dalam beberapa hal "kompleksitas" terakhir adalah "ketidakpastian" alias kelengkapan Turing.)

$n$$x$$n$$x↑n$

$DFA_n$$DFA'$$DFA'$$n$$DFA_n$$DFA'$, juga merupakan RL (dan DFA).

$\Sigma$

$n$$DFA_n ≠ \Sigma*$

$\Sigma*$$n$

sekarang, untuk mengikat ini lebih banyak dengan pertanyaan, sementara ini tidak banyak dicatat (dianggap sepele oleh beberapa), banyak masalah terbuka di TCS / matematika terkait erat dengan ketidakpastian dalam memberikan oracle untuk masalah penghentian, mereka bisa " terpecahkan".

oleh karena itu, dalam arti, mengikat ini bersama-sama menggunakan masalah dasar ini tentang DFA yang tidak dapat diputuskan, akan selalu ada masalah terbuka tentang DFA, karena akan selalu ada masalah "terbuka" tentang DFA (seperti ini) setara dengan masalah yang tidak dapat diputuskan . sebenarnya menggunakan teorema Rices secara terbalik seperti konstruksi ini dalam beberapa hal, pada dasarnya setiap properti komputasi yang relatif "sederhana" namun tidak trivial di TCS dapat digunakan untuk membangun masalah yang tidak dapat diputuskan.

[1] Masalah kata yang membutuhkan waktu eksponensial / Stockmeyer & Meyer

[2] Meyer, AR dan L. Stockmeyer. Masalah kesetaraan untuk ekspresi reguler dengan kuadrat membutuhkan ruang eksponensial. Simposium IEEE ke-13 tentang Switching dan Automata Theory, Okt 1972, hlm.125–129.

[3] Pengantar bahasa, automata dan komputasi / Hopcroft / Ullman.