Dapatkah Mesin Turing memutuskan apakah NFA menerima serangkaian panjang prime?

Saya ingin tahu apakah masalah berikut ini dapat ditentukan:

Instance: NFA A dengan n state

Pertanyaan: Apakah ada beberapa bilangan prima p sehingga A menerima beberapa untaian panjang p.

Keyakinan saya adalah bahwa masalah ini tidak dapat diputuskan, tetapi saya tidak dapat membuktikannya. Penentu dapat dengan mudah memiliki algoritma untuk mencari tahu apakah nomor tertentu adalah prima, tapi saya tidak melihat bagaimana itu akan dapat menganalisis NFA secara cukup detail untuk mengetahui dengan tepat berapa lama dapat dihasilkan. Itu bisa mulai menguji string dengan NFA, tetapi untuk bahasa yang tak terbatas, mungkin tidak pernah berhenti (dan dengan demikian tidak menjadi penentu).

NFA dapat dengan mudah diubah menjadi DFA atau ekspresi reguler jika solusi membutuhkannya, tentu saja.

Pertanyaan ini adalah sesuatu yang telah saya renungkan sebagai pertanyaan persiapan buatan sendiri untuk final yang telah saya buat dalam 2 minggu.

computability finite-automata Dingin
sumber

Saya tidak yakin apakah ini tingkat sarjana, jadi jangan khawatir tentang menghapusnya. Ini mungkin menjadi masalah yang sulit, lihat misalnya terrytao.wordpress.com/2007/05/25/…

Yah, aku mengarangnya, jadi mungkin sulit. Saya belum menemukan bukti masalah yang tidak dapat dipastikan yang melibatkan NFA / DFA, itulah sebabnya saya pikir mungkin menarik untuk mencobanya.

Saya percaya apa yang Anda tautkan adalah masalah yang berbeda (lebih mudah). Itu dapat menjawab "berapa banyak string panjang x yang diterima NFA?". Dengan menggunakan rumus yang disediakan, kita harus memeriksa banyak contoh untuk melihat apakah ada string yang diterima NFA yang panjangnya prima. Saya tidak bertanya tentang prime tertentu, saya bertanya tentang mereka semua.

s_{L} (n)

$s_L(n)$

Jawaban:

Panjang string yang diterima oleh DFA membentuk satu set semilinear (seperti dalam teorema Parikh untuk bahasa bebas konteks), deskripsi dari mereka tidak terlalu sulit didapat (dasarnya memisahkan semua kemungkinan siklus otomat), dan oleh Teorema Dirichlet setiap perkembangan aritmatika dari bentuk dengan berisi infinitude bilangan prima. $a + b k$ $\gcd(a, b) = 1$

Menarik di atas bersama-sama memberikan algoritma untuk memeriksa apakah bahasa bebas reguler Anda (atau bahkan konteks) berisi string dengan panjang prima. Jelas bukan pertanyaan sederhana, IMVHO ...

vonbrand
sumber

Saya menghargai bantuan yang memahami teorema Parikh dalam contoh ini. Kita jelas dapat mengubah NFA menjadi PDA dengan tidak menggunakan tumpukan di PDA. Apakah himpunan bagian linier menentukan siklus? Jika demikian, bagaimana cara kerjanya?

Dinginkan

@ Chill, Pertimbangkan jalur apa pun melalui DFA. Ini mungkin langsung dari keadaan awal ke kondisi akhir, atau mungkin berulang. Panjang string yang mungkin ditentukan oleh "bagian lurus" + jumlah kali "panjang loop yang mungkin" untuk arbitrary s. Hanya menggambar beberapa kusut DFA, dan lacak jalur melalui itu. Anda akan melihat panjang yang mungkin jatuh ke dalam keluarga urutan aritmatika yang ditentukan oleh siklus, yaitu, mereka membentuk set semilinear. Tidak perlu pergi konteks gratis (hanya bonus gratis yang bagus).

k

$k$

k

$k$

vonbrand

Saya pikir itu menjawab pertanyaan saya. Saya akan mencoba membaca lebih banyak tentang teorema Parikh. Saya mengerti ide itu dan bagaimana ia dapat menentukan siklus dalam kasus ini. Apa yang saya ingin cari tahu adalah solusi yang lebih "langsung" di mana saya membuat algoritma yang sebenarnya untuk memecahkan masalah ini.

Dinginkan

@ Chill, lihat saja komentar saya sebelumnya. Tidak terlalu sulit untuk menghasilkan deskripsi panjang yang mungkin dengan hanya menghapus simbol pada DFA sebagai grafik dan memeriksa jalan-jalan antara keadaan mulai awal dan keadaan akhir. Sulit untuk diformalkan, mudah dipecahkan dengan tangan untuk contoh yang diberikan.

vonbrand

@dkuper, tidak sesederhana itu. Bahasa biasa tidak terbatas, tetapi tidak mengandung string dengan panjang prima.

a a a a (a a)^{*}

$a a a a (a a)^*$

vonbrand