Kondisi untuk universalitas NFA

Pertimbangkan automata terbatas nondeterministic , dan fungsi . Selain itu kami mendefinisikan .$A = (Q, \Sigma, \delta, q_0, F)$$f(n)$$\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$

Sekarang mari kita menganalisis pernyataan berikut:

Jika , maka .$\Sigma^{\leq f(|Q|)} \subseteq L(A)$$L(A) = \Sigma^*$

Sangat mudah untuk menunjukkan, bahwa untuk $f(n) = 2^n+1$ itu benar, maka jika automata menghasilkan setiap kata dengan panjang upto $2^{|Q|}+1$ , maka menghasilkan .$\Sigma^*$

Tetapi apakah itu masih berlaku jika adalah polinom?$f$

Jika tidak, seperti apa konstruksi NFA untuk polinom terlihat, st ?$A$$p$$\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^*$

Agar pernyataan tetap berlaku, f harus tumbuh secara eksponensial, bahkan dengan alfabet unary

[Sunting: Analisis sedikit ditingkatkan dalam revisi 2.]

Ini sketsa bukti. Misalkan pernyataan itu memegang dan membiarkan f menjadi fungsi sedemikian rupa sehingga setiap NFA dengan paling banyak n menyatakan yang menerima semua string dengan panjang paling banyak f ( n ) menerima semua string apa pun. Kami akan membuktikan bahwa untuk setiap C > 0 dan cukup besar n , kami memiliki f ( n )> 2 ^{C ⋅√ n} .

The prima Teorema menyiratkan bahwa untuk setiap c <lg e dan cukup besar k , setidaknya ada c ⋅2 ^k / k bilangan prima dalam rentang [2 ^k , 2 ^{k 1} ]. Kami mengambil c = 1. Untuk seperti k , biarkan N _k = ⌈2 ^k / k ⌉ dan mendefinisikan NFA M _k sebagai berikut. Biarkan p ₁ , ..., p _{N k} menjadi bilangan prima yang berbeda dalam rentang [2 ^k , 2 ^{k 1}] NFA M _k memiliki S _k = 1 + p ₁ + ... + p _{N k} negara. Terlepas dari keadaan awal, negara-negara yang dipartisi menjadi N _k siklus di mana saya siklus th memiliki panjang p _i . Dalam setiap siklus, semua kecuali satu negara adalah negara yang diterima. Awal negara memiliki N _k tepi keluar, yang masing-masing pergi ke negara segera setelah negara ditolak pada setiap siklus. Akhirnya, kondisi awal juga diterima.

Biarkan P _k menjadi produk p ₁ ... p _{N k} . Sangat mudah untuk melihat bahwa M _k menerima semua string dengan panjang kurang dari P _k tetapi menolak string panjang P _k . Oleh karena itu, f ( S _k ) ≥ P _k .

Perhatikan bahwa S _k ≤ 1 + N _k ⋅2 ^{k +1} = o (2 ^{2 k} ) dan P _k ≥ (2 ^k ) ^{N _k} ≥ 2 ^{2 k} . Sisanya standar.

EDIT PADA 10/12/06:

ok, ini cukup banyak konstruksi terbaik yang bisa saya dapatkan, lihat apakah ada yang punya ide yang lebih baik.

Dalil. Untuk setiap Ada ( 5 n + 12 ) -negara NFA M lebih dari huruf Σ dengan | Σ | = 5 sehingga string terpendek yang tidak dalam L ( M ) adalah panjang ( 2 n - 1 ) ( n + 1 ) + 1 .$n$$(5n+12)$$M$$\Sigma$$|\Sigma|=5$$L(M)$$(2^n-1)(n+1)+1$

Ini akan memberi kita .$f(n) = \Omega(2^{n/5})$

Konstruksinya hampir sama dengan yang ada di Shallit , kecuali kami membangun NFA secara langsung alih-alih mewakili bahasa dengan ekspresi reguler terlebih dahulu. Membiarkan

$\Sigma = \{{0 \brack 0},{0 \brack 1},{1 \brack 0},{1 \brack 1},\sharp\}$ .

Untuk setiap , kita akan membangun bahasa pengenal NFA , di mana adalah urutan berikut (ambil misalnya):Σ ∗ - { s n } s n n = $n$$\Sigma^*-\{s_n\}$$s_n$$n=3$

$s_3 = \sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp{0 \brack 0}{0 \brack 1}{1 \brack 0}\sharp \ldots \sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$ .

Idenya adalah bahwa kita dapat membangun NFA terdiri dari lima bagian;

• a pemula , yang menjamin string dimulai dengan ;$\sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp$
• sebuah terminator , yang menjamin ujung string dengan ;$\sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$
• sebuah penghitung , yang membuat jumlah simbol antara dua sebagai ;$\sharp$$n$
• pemeriksa add-one , yang menjamin bahwa hanya simbol dengan bentuk muncul; akhirnya,$\sharp{x \atop x+1}\sharp$
• sebuah checker yang konsisten , yang menjamin bahwa hanya simbol dengan bentuk dapat muncul secara bersamaan.$\sharp{x \atop y}\sharp{y \atop z}\sharp$

Perhatikan bahwa kami ingin menerima alih-alih , jadi setelah kami mengetahui bahwa urutan input tidak mematuhi salah satu perilaku di atas, kami segera menerima urutannya. Kalau tidak, setelahlangkah-langkah, NFA akan menjadi satu-satunya negara yang menolak. Dan jika urutannya lebih panjang dari, NFA juga menerima. Jadi, setiap NFA yang memenuhi lima syarat di atas hanya akan menolak .{ s n } | s n | | s n | s $\Sigma^*-\{s_n\}$$\{s_n\}$$|s_n|$$|s_n|$$s_n$

Mungkin mudah untuk memeriksa gambar berikut secara langsung, bukan bukti keras:

Kami mulai di negara bagian kiri atas. Bagian pertama adalah starter, dan penghitung, kemudian pemeriksa konsisten, terminator, akhirnya pemeriksa add-one. Semua busur tanpa titik terminal menunjuk ke status kanan bawah, yang merupakan akseptor sepanjang masa. Beberapa tepi tidak diberi label karena kurangnya ruang, tetapi dapat dipulihkan dengan mudah. Garis putus-putus mewakili urutan status dengan tepi .n - $n-1$$n-2$

Kami dapat (dengan susah payah) memverifikasi bahwa NFA hanya menolak , karena NFA mengikuti semua aturan di atas. Jadi NFA -state dengan telah dibangun, yang memenuhi persyaratan teorema.$s_n$$(5n+12)$$|\Sigma|=5$

Jika ada ketidakjelasan / masalah dengan konstruksi, silakan tinggalkan komentar dan saya akan mencoba menjelaskan / memperbaikinya.

Pertanyaan ini telah dipelajari oleh Jeffrey O. Shallit et al., Dan memang nilai optimal dari masih terbuka untuk . (Adapun bahasa unary, lihat komentar dalam jawaban Tsuyoshi )$f(n)$$|\Sigma|>1$

Dalam halaman 46-51 ceramahnya tentang universalitas , ia memberikan konstruksi sedemikian rupa sehingga:

Dalil. Untuk untuk beberapa cukup besar, ada -state NFA atas huruf biner sehingga string terpendek yang tidak dalam adalah panjangnya untuk .$n\geq N$$N$$n$$M$$L(M)$$\Omega(2^{cn})$$c=1/75$

Jadi nilai optimal untuk berada di antara dan . Saya tidak yakin apakah hasilnya oleh Shallit telah ditingkatkan dalam beberapa tahun terakhir.$f(n)$$2^{n/75}$$2^n$