Algoritma untuk mengkonversi NFA yang sangat besar ke DFA

Saya memiliki otomat terbatas non-deterministik yang sangat besar dan saya perlu mengubahnya ke DFA.

Secara umum saya maksudkan 40 000+ negara bagian. Sejauh ini saya telah melakukan beberapa percobaan dan memprogram algoritma default yang mencari melalui tabel (seperti dijelaskan di sini ), tetapi bahkan setelah optimasi cukup lambat dan sangat memakan memori. Saya menyadari fakta, bahwa jumlah negara dapat tumbuh secara eksponensial, tetapi setelah minimalisasi, DFA yang dihasilkan memiliki sekitar 9.000 negara dan itu dapat ditoleransi.

Jadi pertanyaan saya adalah, apakah ada beberapa algoritma, yang akan lebih cepat atau lebih ramah memori?

Sudahkah Anda mencoba algoritma Brzozowski ? Waktu berjalan terburuk adalah eksponensial, tetapi saya melihat beberapa referensi yang menunjukkan bahwa itu sering berkinerja sangat baik, terutama ketika memulai dengan NFA yang ingin Anda konversi ke DFA dan meminimalkan.

Makalah berikut ini tampaknya relevan:

• Pada kinerja algoritma minimisasi automata , Marco Almeida, Nelma Moreira, Rogerio Reis.

Ini mengevaluasi sejumlah algoritma yang berbeda untuk minimalisasi DFA, termasuk aplikasi mereka untuk situasi Anda di mana kami mulai dengan NFA dan ingin mengubahnya menjadi DFA dan menguranginya.

Seperti apa dekomposisi komponen yang sangat terhubung (SCC) NFA Anda (menganggapnya sebagai grafik berarah)? Apakah ada banyak komponen, di mana tidak ada komponen yang terlalu besar? Jika demikian, saya bertanya-tanya apakah mungkin untuk merancang algoritma divide-and-conquer, di mana Anda mengambil satu komponen, mengonversinya dari NFA ke DFA dan kemudian menguranginya, dan kemudian mengganti yang asli dengan versi yang ditentukan baru. Ini harus dimungkinkan untuk komponen entri-tunggal (di mana semua tepi ke dalam komponen itu mengarah ke satu simpul, simpul entri). Saya tidak segera melihat apakah mungkin untuk melakukan sesuatu seperti ini untuk NFA sewenang-wenang, tetapi jika Anda memeriksa seperti apa struktur SCC, maka Anda mungkin dapat menentukan apakah arah semacam ini layak dijelajahi atau tidak .

ini tampaknya bukan masalah yang dipelajari dengan sangat baik dalam arti algoritma yang dikenal / tersedia selain dari strategi asli / lama dari "determinize to DFA / meminimalkan DFA". Anda tampaknya menunjukkan langkah determinisasi adalah yang bermasalah, tetapi ini khas tentu saja karena memiliki kasus eksponensial-ruang / waktu yang lebih buruk. perhatikan bahwa ada beberapa algoritma minimalisasi DFA yang dapat bervariasi secara signifikan dalam kinerja rata-rata.

itu juga dikenal lebih informal sebagai "minimalisasi NFA tanpa determinasi" . diketahui sulit dalam arti bahwa pada dasarnya bahkan tidak ada algoritma perkiraan kecuali P = Pspace seperti yang ditunjukkan dalam makalah ini:

• Meminimalkan NFA dan Ekspresi Reguler oleh Gregor Gramlich, Georg Schnitger

Namun makalah ini tidak mempertimbangkan kasus yang umumnya jarang dieksplorasi dari beberapa algoritma yang tidak didasarkan pada penemuan DFA 1 ^{st yang} ditentukan :

• Algoritma reduksi NFA melalui ketidaksetaraan reguler Jean-Marc Champarnaud, Fabien Coulon

Kami menyajikan berbagai teknik untuk mengurangi jumlah status dan transisi dalam automata non-deterministik. Teknik-teknik ini didasarkan pada dua preorder atas set negara, terkait dengan dimasukkannya bahasa kiri dan kanan. Karena perhitungan yang tepat adalah NP-hard, kami fokus pada pendekatan polinomial yang memungkinkan pengurangan NFA semua sama.

catat paket / implementasi yang tersedia untuk umum yang dapat menangani konversi / minimasi NFA / DFA besar dll secara umum seefisien mungkin adalah perpustakaan AT&T FSM .

ia memiliki strategi fsmcompactyang terkadang cukup:

Dalam kasus di mana transduser atau akseptor berbobot tidak dapat ditentukan atau tumbuh sangat besar, optimasi yang berbeda mungkin bermanfaat - fsmcompact. Operasi ini mengkodekan setiap tiga kali lipat dari label input, label output dan biaya menjadi satu label baru, melakukan determinasi klasikisasi dan minimalisasi, dan kemudian menerjemahkan kode label yang dikodekan kembali ke nilai aslinya. Ini memiliki keunggulan yang selalu didefinisikan dan tidak memindahkan label atau biaya output di sepanjang jalur. Ini memiliki kelemahan bahwa hasilnya tidak dapat menjadi deterministik atau minimal.