Berapa jumlah bahasa yang diterima oleh DFA ukuran

19

Pertanyaannya sederhana dan langsung: Untuk tetap , berapa banyak (berbeda) bahasa diterima oleh DFA ukuran n (yaitu n negara)? Saya akan secara resmi menyatakan ini:nnn

Tentukan DFA sebagai , di mana semuanya seperti biasa dan δ : Q × Σ Q adalah fungsi (mungkin sebagian). Kita perlu menetapkan ini karena terkadang hanya total fungsi yang dianggap valid.(Q,Σ,δ,q0,F)δ:Q×ΣQ

Untuk setiap , tentukan hubungan (ekivalensi) n pada himpunan semua DFA sebagai: A n B jika | A | = | B | = n dan L ( A ) = L ( B ) .n1nAnB|A|=|B|=nL(A)=L(B)

Pertanyaannya adalah, kemudian: untuk diberikan , berapakah indeks n ? Artinya, berapa ukuran himpunan { L ( A ) A  adalah DFA ukuran  n } ?nn{L(A)A is a DFA of size n}

Bahkan ketika adalah fungsi total, sepertinya itu bukan perhitungan yang mudah (bagi saya, setidaknya). Grafik mungkin tidak terhubung, dan keadaan dalam komponen terhubung yang mengandung keadaan awal mungkin semuanya menerima, jadi, misalnya, ada banyak grafik ukuran n menerima Σ . Sama dengan kombinasi sepele lainnya untuk bahasa kosong dan bahasa lain yang DFA minimalnya memiliki lebih sedikit dari n status.δnΣn

Rekursi (naif) juga tampaknya tidak berhasil. Jika kita mengambil DFA ukuran dan menambahkan status baru, maka, jika kita ingin tetap determinisme dan membuat grafik baru terhubung (untuk menghindari kasus-kasus sepele), kita harus menghapus transisi untuk menghubungkan status baru, tetapi dalam hal ini kita mungkin kehilangan bahasa aslinya.k

Adakah pikiran?

Catatan. Saya memperbarui pertanyaan lagi, dengan pernyataan resmi dan tanpa unsur-unsur yang mengganggu sebelumnya.

Janoma
sumber
Hanya untuk memperjelas: Apakah maksud Anda "berapa banyak bahasa yang berbeda yang dapat didefinisikan oleh seseorang menggunakan negara?", Di mana bahasa didefinisikan menggunakan n negara jika ada DFA dengan nnnn state yang menerimanya. Juga, untuk ekspresi reguler, regex "a * aaaaaa" pasti memiliki> 1 concatenations, tetapi DFA hanya membutuhkan satu negara (dua jika Anda memerlukan wastafel terpisah), bukan?
Evgenij Thorstensen
Permintaan maaf: Untuk contoh regex, itu harus " a a a a *", karena hal itu memungkinkan angka apa pun.
Evgenij Thorstensen
Definisi dari muncul sangat terkait dengan gagasan "dot-depth", kecuali konsep itu biasanya diterapkan pada bahasa bebas bintang (mungkin karena alasan yang diuraikan oleh @Evgenij Thorstensen). c(r)
mhum
1
Pengamatan sepele: negara dapat digunakan untuk mendefinisikan setidaknya 2 n bahasa yang berbeda. n+12n
Evgenij Thorstensen
2
Kita bisa mendapatkan sedikit lebih banyak, jadi tampaknya OK. Tetapi jumlah automata n-state sekitar n c n 2 n = 2 c n log n + n = 2 Θ ( n log n ) (dengan asumsi | Σ | = c ). Bisakah kita mendapatkan 2 ω ( n ) ? 2Ω(n)ncn2n=2cnlogn+n=2Θ(nlogn)|Σ|=c2ω(n)
Kaveh

Jawaban:

20

Saya pikir pertanyaan ini sudah dipelajari sebelumnya. Mike Domaratzki menulis survei tentang penelitian di bidang ini: "Pencacahan Bahasa Formal", Bull. EATCS, vol. 89 (Juni 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf

Hermann Gruber
sumber
4
Makalah ini menjawab dengan tepat pertanyaan yang diajukan, dari halaman 120 dan seterusnya. Ini fungsi , dan kertasnya memberikan batas yang agak ketat (dekat dengan apa yang Kaveh sebutkan di atas) di atasnya, meskipun saya belum menghirup semua detailnya. gk(n)
Evgenij Thorstensen
1
Memang. Apa yang kita inginkan, adalah , atau, dengan hubungan yang diberikan, f k ( n ) , yang merupakan jumlah DFA minimal non-isomorfik berpasangan dengan n menyatakan lebih dari alfabet k- newsletter. Saya belum melihatnya secara rinci, tetapi tampaknya hanya batas yang diketahui, bukan jumlah yang pasti. gk(n)fk(n)nk
Janoma
6
Dan, dari penulis yang sama, kami memiliki artikel tentang Jumlah Bahasa yang Berbeda yang Diterima oleh Finite Automata dengan n Negara , yang bahkan memberikan perhitungan eksplisit untuk ( 1 n 10 ), g 2 ( n ) ( 1 n 6 ) dan g 3 ( n ) ( 1 n 4 ). g1(n)1n10g2(n)1n6g3(n)1n4
Janoma