Bagaimana kondisi NFA agar ukuran DFA ekivalennya maksimal?

Kita tahu bahwa DFA setara dengan NFA dalam kekuatan ekspresif; ada juga algoritma yang dikenal untuk mengubah NFA menjadi DFA (sayangnya saya sekarang tahu penemu algoritma itu), yang dalam kasus terburuk memberi kita status , jika NFA kami memiliki status $2^S$ $S$

Pertanyaan saya adalah: apa yang menentukan skenario terburuk?

Berikut adalah transkripsi algoritma jika terjadi ambiguitas:

Biarkan menjadi NFA. Kami membuat DFA mana $A = (Q,\Sigma,\delta,q_0,F)$ $A' = (Q',\Sigma,\delta',q'_0,F')$

$Q' = \mathcal{P}(Q)$ ,
$F' = \{S \in Q' | F \cap S \neq \emptyset \}$ ,
$\delta'(S,a) =\bigcup_{s \in S} (\delta(s,a) \cup \hat \delta(s,\varepsilon))$ , dan
$q'_0 = \{q_0\} \cup \hat \delta(q_0, \varepsilon)$ ,

mana adalah fungsi transisi diperpanjang . $\hat\delta$ $A$

formal-languages automata regular-languages finite-automata nondeterminism Daniil
sumber

sebagai komentar menyatakan Anda bisa menyelamatkan Q ini dengan meminta "minimal" NFA untuk DFA (masalah terbuka). selalu berpikir masalah ini terkait erat dengan P =? NP pertanyaan dalam berbagai cara & memiliki beberapa formulasi serupa yang menyarankan itu. ini serupa dengan yang Anda tanyakan tentang DFA "kompresibel" vs "tidak kompresibel" di mana "tidak dapat dipampatkan" adalah kasus terburuk sehingga NFA minimal hampir sebesar DFA. mungkin ada beberapa teorema seperti, "sebagian besar DFA, diambil secara acak, tidak dapat dimampatkan [ke NFA]" karena ada teori serupa dalam teori informasi tentang kompleksitas string string dll.

vzn

Jawaban:

Algoritma yang Anda rujuk disebut Konstruksi Powerset, dan pertama kali diterbitkan oleh Michael Rabin dan Dana Scott pada tahun 1959.

Untuk menjawab pertanyaan Anda seperti yang dinyatakan dalam judul, tidak ada maksimal DFA untuk bahasa biasa, karena Anda selalu dapat mengambil DFA dan menambahkan sebanyak negara yang Anda inginkan dengan transisi antara mereka, tapi tanpa transisi antara salah satu asli negara dan salah satu yang baru. Dengan demikian, negara-negara baru tidak akan dicapai dari keadaan awal , sehingga bahasa diterima oleh robot tidak akan berubah (karena akan tetap sama untuk semua ). $q_0$ $\hat\delta(q_0,w)$ $w\in\Sigma^*$

Yang mengatakan, jelas bahwa tidak ada kondisi pada NFA untuk yang setara DFA menjadi maksimal, karena tidak ada yang unik setara DFA. Sebaliknya, DFA minimal unik hingga isomorfisma.

Contoh kanonik bahasa yang diterima oleh NFA dengan menyatakan dengan DFA setara dengan menyatakan adalah Sebuah NFA untuk adalah $n+1$ $2^n$

L = {w \in {0, 1}^{*} : | w | \geq n and the n -th symbol from the last one is 1} .

$L=\{w\in\{0,1\}^*:|w|\geq n\text{ and the $n$-th symbol from the last one is 1}\}.$

L

$L$

, dengan

dan

untuk

A = ⟨ Q, {0, 1}, δ, q_{0}, {q_{n + 1}} ⟩

$A=\langle Q,\{0,1\},\delta,q_0,\{q_{n+1}\}\rangle$

δ (q_{0}, 0) = {q_{0}}

$\delta(q_0,0)=\{q_0\}$

δ (q_{0}, 1) = {q_{0}, q_{1}}

$\delta(q_0,1)=\{q_0,q_1\}$

δ (q_{i}, 0) = δ (q_{i}, 1) = {q_{i + 1}}

$\delta(q_i,0)=\delta(q_i,1)=\{q_{i+1}\}$

. DFA dihasilkan dari penerapan pembangunan Powerset untuk NFA ini akan memiliki

negara, karena Anda perlu untuk mewakili semua

kata-kata panjang

sebagai akhiran dari kata dalam

i \in {1, \dots, n}

$i\in\{1,\ldots,n\}$

2^{n}

$2^n$

2^{n}

$2^n$

n

$n$

L

$L$

Janoma
sumber

Ngomong-ngomong, jika Anda ingin tanda kurung keriting muncul dalam mode tampilan matematika gunakan \\ {dan \\}.

Zach Langley

@ ZachLangley Saya sudah mencoba, itu tidak berhasil :-(

Janoma

Tampaknya berfungsi untuk saya di pratinjau. Saya tidak dapat mengirimkan hasil edit, karena saya hanya menambahkan empat karakter dan minimum enam. Anda menggunakan dua garis miring terbalik dan tidak berhasil?

Zach Langley

@ZachLangley Berhasil sekarang, tetapi ada dua hal: pertama, tidak berhasil ketika saya pertama kali memposting jawabannya. 2, saya pikir ini tidak konsisten dengan perilaku rendering LaTeX di cstheory, tapi saya mungkin salah.

Janoma

DFA yang dihasilkan minimal? Bisakah Anda berbicara sedikit tentang cara membuktikan bahwa itu minimal?

user834

$2^{s}$ $\{a, b\}$ $a$ $b$ $a$ $b$ $\lambda$ $a$ $b$ $ab$ $\{q_{1}\}$ $\{q_{2}\}$ $\{\}$ $\{q_{1}, q_{2}\}$

Patrick87
sumber

setuju tetapi pertanyaan "apakah ada cara untuk sampai ke setiap bagian yang mungkin dari negara bagian di NFA" adalah nontrivial & layak untuk dipelajari lebih lanjut ....

vzn

-1

Saya percaya ini adalah pertanyaan di garis depan pengetahuan, yaitu pada dasarnya pertanyaan penelitian. Dari pencarian google cepat, tampaknya sebagian besar terbuka. Juga, selama bertahun-tahun saya percaya itu penting dan terkait dengan teori kompleksitas batas bawah. Anda tidak menyebutkan secara langsung analisis statistik tetapi itulah yang tersirat oleh pertanyaan Anda. Berikut adalah dua contoh studi statistik tentang DFA / NFA yang mirip dengan menunjukkan pendekatan umum untuk pertanyaan jenis ini. Tampaknya penelitian empiris dasar terhadap pertanyaan-pertanyaan seperti ini sebagian besar masih belum dijelajahi. Memang yang ke-2 tidak berhubungan langsung dengan pertanyaan Anda, tetapi yang paling dekat yang bisa saya temukan dari penelitian saat ini.

$x$

Metrik ini akan terkait dengan metrik teori grafik seperti kerapatan tepi dan sebagainya. Mungkin ada beberapa metrik teori grafik yang sangat penting atau campuran metrik yang memperkirakan "ledakan" tetapi tidak segera jelas bagi saya. Saya bisa menyarankan sesuatu seperti metrik pewarnaan grafik atau metrik klik mungkin. Kemudian uji metrik terhadap dua set "meledakkan" vs "tidak meledak".

Jawaban lain untuk pertanyaan Anda sejauh ini hanya memberikan contoh kasus "ledakan" (berguna untuk studi kasus) tetapi tidak membahas masalah utama metrik umum.

Bidang lain untuk melihat program penelitian empiris yang berhasil dikembangkan adalah penelitian titik transisi SAT. Itu telah mengembangkan hubungan yang sangat dalam dengan konsep fisika dan termodinamika. Tampaknya bagi saya konsep yang sama berlaku di sini. Misalnya, seseorang cenderung menemukan metrik jenis titik transisi analog; mungkin kerapatan tepi dll. Perhatikan persamaan dengan teori kompresibilitas Kolmogorov.

Saya menduga juga bahwa NFA yang "meledakkan" vs yang tidak cukup analog entah bagaimana dengan "sulit" vs "mudah" contoh masalah NP-lengkap.

Namun cara lain untuk mempelajari masalah ini adalah dengan merumuskan masalah minimalisasi NFA. Artinya, diberi DFA, temukan NFA minimal, yang terakhir saya dengar (bertahun-tahun lalu) masih menjadi masalah terbuka.

[1] Tentang kinerja algoritma minimisasi automata Marco Almeida, Nelma Moreira, Rogério Reis

[2] Automata Mengenali Tanpa Kata: Suatu Pendekatan Statistik Cristian S. Calude, Cezar Câmpeanu, Monica Dumitrescu

ay
sumber