Automata terbatas yang menerima string biner dapat dibagi oleh n

18

Saya sedang mengerjakan set masalah untuk kelas, dan memikirkan pertanyaan terkait dengan apa yang saya kerjakan. Apakah ada jumlah minimum status yang harus dimiliki otomat terbatas untuk menerima string biner yang mewakili angka yang dapat dibagi oleh bilangan bulat n? Dalam set masalah sebelumnya, saya bisa membangun DFA yang menerima string biner dibagi 3 dengan 3 status. Apakah ini kebetulan, atau adakah sesuatu yang inheren dengan masalah umum mendeteksi string yang dapat dibagi oleh n yang menunjukkan jumlah minimum negara?

Saya berjanji ini tidak akan menjawab pertanyaan pekerjaan rumah untuk saya! :)

automata-theory Nick Van Hoogenstyn
sumber
3
Selamat datang di cstheory, situs tanya jawab untuk pertanyaan tingkat penelitian dalam ilmu komputer teoretis (TCS). Pertanyaan Anda tampaknya bukan pertanyaan tingkat penelitian di TCS. Silakan lihat FAQ untuk informasi lebih lanjut tentang apa yang dimaksud dengan ini dan saran untuk situs yang mungkin menyambut pertanyaan Anda. Akhirnya, jika pertanyaan Anda ditutup karena berada di luar jangkauan, dan Anda yakin Anda dapat mengedit pertanyaan untuk menjadikannya pertanyaan tingkat penelitian, jangan ragu untuk melakukannya. Penutupan tidak permanen dan pertanyaan dapat dibuka kembali, periksa FAQ untuk informasi lebih lanjut.
Kaveh
2
@ Kaveh: Saya pikir pertanyaannya baik-baik saja, terutama mengingat jawaban singkat David.
Huck Bennett
2
@HuckBennett Saya setuju dengan Kaveh bahwa pertanyaan ini harus ditutup pada cstheory, sebagian besar harus konsisten. Namun, saya juga setuju dengan Anda: ini adalah pertanyaan yang menyenangkan dan ketika Anda pertama kali melihat DFA, itu pasti salah satu yang harus Anda tanyakan pada diri sendiri. Saya pikir OP harus mencoba bersenang-senang mengerjakan jawabannya sendiri, dan kemudian berkonsultasi dengan math.SE untuk info lebih lanjut.
Artem Kaznatcheev
11
Ini bukan pekerjaan rumah (meskipun diilhami oleh pertanyaan pekerjaan rumah), ini pertanyaan yang menarik, saya tidak percaya itu adalah hasil yang terkenal dan jawaban untuk pertanyaan itu muncul dalam jurnal penelitian. Saya tidak mengerti mengapa itu harus ditutup. Batas atas adalah pekerjaan rumah, dan memang mudah, tetapi pertanyaannya adalah tentang batas bawah.
Peter Shor
1
@ Janoma: Memang. Akhir pertanyaan menyarankan OP membingungkan batas atas dengan batas bawah.
Michael Blondin

Jawaban:

32

nR

nRnn

David Harris
sumber
1
Hal yang persis seperti yang saya cari. Terima kasih, saya akan terjun ke koran dalam waktu dekat.
Nick Van Hoogenstyn
2
Tautannya tampaknya rusak
gigabytes
8

Ada makalah lain tentang masalah yang sama: B. Alexeev, Minimal DFA untuk menguji keterbelahan, J. Comput. Syst. Sci. 69 (2004), 235-243.

Jeffrey Shallit
sumber