Jumlah DFA minimal ukuran paling banyak ?

Biarkan menjadi alfabet ukuran , dan pertimbangkan DFA minimal yang ukurannya dibatasi paling banyak . Misalkan menunjukkan jumlah DFA minimal yang berbeda. $\Sigma$ $2$ $m$ $f(m)$

Bisakah kita menemukan rumus bentuk tertutup untuk ? $f(m)$

Menimbang bahwa untuk fungsi transisi dari DFA ukuran paling banyak adalah grafik. Karena derajat node dibatasi oleh , untuk setiap node ada kemungkinan pasangan busur (seperti yang disarankan dalam komentar). Dalam grafik ini ada paling banyak pilihan yang mungkin dari keadaan awal dan paling banyak kemungkinan pilihan set keadaan akhir. Dengan demikian, jumlah maksimum DFA ukuran paling banyak adalah . $|\Sigma|=2$ $m$ $2$ $m^2$ $m$ $2^m$ $m$ $f(m) \leq m^{2m}\cdot m\cdot2^m = 2^m\cdot m^{2m+1}$

Kita dapat menggeneralisasi ke alfabet arbitrer : batas menjadi . $\Sigma$ $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$

Tapi kami terikat di sini DFA sewenang-wenang dan saya tertarik untuk membatasi jumlah DFA minimal. Jadi, sepertinya ikatan ini bisa lebih ketat ... Apakah seseorang memiliki perkiraan yang lebih baik?

Saya akan menghargai jika memungkinkan, beberapa makalah terkait dengan masalah ini atau bukti / contoh tandingan.

cc.complexity-theory automata-theory nondeterminism dfa Luz
sumber

Saya tidak berpikir batas atas Anda benar. Sepertinya seharusnya , bukan . Untuk setiap simpul, pertimbangkan dua busur yang keluar dari simpul itu; ada kemungkinan untuk ke mana busur pertama pergi, dan kemungkinan untuk ke mana busur kedua pergi, jadi kemungkinan secara total. Ada node, jadi kami memperoleh kemungkinan untuk set busur. Generalisasi akan menjadi .

f (m) \leq m \times 2^{m} \times m^{2 m}

$f(m) \le m \times 2^m \times m^{2m}$

f (m) \leq m \times 2^{m} \times 2^{2 m}

$f(m) \le m \times 2^m \times 2^{2m}$

m

$m$

m

$m$

m^{2}

$m^2$

m

$m$

(m^{2})^{m} = m^{2 m}

$(m^2)^m = m^{2m}$

f (m) \leq m \times 2^{m} \times m^{| Σ | m}

$f(m) \le m \times 2^m \times m^{|\Sigma| m}$

Berikut ini adalah referensi yang dapat dirilis: "PADA JUMLAH BAHASA YANG

BERBEDA

Terima kasih kepada Anda berdua untuk memperbaiki kesalahan saya dan memberi saya referensi ini yang memang relevan.

Luz

Jawaban:

Menurut Ishigami Y., Tani S. (1993) VC-dimensi automata terbatas dengan negara n, http://link.springer.com/chapter/10.1007/3-540-57370-4_58 , VC-dimensi dimensi kelas konsep status DFA di atas alfabet ukuran adalah Oleh karena itu ada setidaknya otata status yang berbeda pada alfabet -letter. Batas atas pada nomor automata tersebut mengikuti dari argumen penghitungan sederhana (diberikan dalam makalah), dan paling banyak . $n$ $k$

d = d (n, k) := (k - 1 + o (1)) n \log_{2} n .

$d=d(n,k) := (k-1+o(1))n\log_2 n.$

2^{d}

$2^d$

n

$n$

k

$k$

2^{d}

$2^d$

Aryeh
sumber

Terima kasih. Saya mengerti dari jawaban Anda bahwa ada menyatakan DFA (paling tidak dan paling banyak). Tapi saya tertarik menghitung DFA minimal. Jadi batas atas Anda tidak bertentangan dengan yang diberikan dalam jawaban saya, bukan?

m^{(| Σ | - 1 + o (1)) m}

$m^{(|\Sigma| - 1 + o(1)) m}$

m

$m$

Luz

Saya pikir ini menghitung DFA minimal juga, karena dimensi VC adalah representasi-independen, itu sebenarnya menghitung bahasa yang berbeda - yang sesuai dengan DFA minimal.

Aryeh

oh :( maka ikatanmu bertentangan dengan milikku ... karena milikku memiliki penyebut besar yang membuatnya jauh di bawah milikmu ... bagaimana bisa ??

(m - 1)!

$(m-1)!$

Luz

Saya tidak begitu melihat kontradiksi - penyebut besarmasih dibanjiri oleh di pembilang.

(m - 1)!

$(m-1)!$

m^{m}

$m^m$

Aryeh

Bahkan, jika Anda melihat bukti Thm. 3,2 di kertas yang saya tautkan, Anda akan melihat ekspresi yang tepat di penyebutnya.

Aryeh

(NB: batas atas yang diberikan dalam jawaban yang diterima lebih baik atau sama dengan yang diberikan di sini)

Batas atas diusulkan dalam makalah ini diberikan dalam salah satu komentar sebelumnya: " Pada jumlah bahasa yang berbeda yang diterima oleh automata terbatas dengan n negara " (2002, M. Domaratzki, D. Kisman, J. Shallit) .

Dalam makalah ini:

yang fungsi menyediakan jumlah yang berbeda DFAs minimal non-isomorfik dengan -states selama -surat alfabet , $f_{|\Sigma|}(m)$ $m$ ${|\Sigma|}$
fungsi memberikan jumlah bahasa berbeda yang diterima oleh DFA dengan menyatakan lebih dari alfabet -letter . $g_{|\Sigma|}(m)$ $m$ ${|\Sigma|}$

Kami tertarik pada batas atas untuk fungsi , karena pertanyaan saya meminta batas atas pada jumlah DFA minimal dengan paling banyak state (dan bukan tepatnya ). $g_{|\Sigma|}(m)$ $m$ $m$

Apa yang saya pahami dari halaman bawah Teorema adalah yang merupakan batas yang lebih baik daripada yang diberikan dalam pertanyaan saya (yaitu ). Ini sebagian menjawab pertanyaan saya. $6$ $8$ $g_{|\Sigma|}(m) \leq \frac{2^m\cdot m^{|\Sigma|m}}{(m-1)!}$ $2^m\cdot m^{|\Sigma|m+1}$

Tetapi makalah ini mengklaim bahwa batas atas ini sepele dan dapat ditingkatkan. Namun, peningkatan hanya berkaitan dengan (sejauh yang saya mengerti). $f_{|\Sigma|}(m)$

Luz
sumber