Mengapa minimalisasi NFA merupakan masalah yang sulit ketika minimasi DFA tidak?

Saya tahu bahwa kami dapat meminimalkan DFA dengan menemukan dan menggabungkan status yang setara, tetapi mengapa kami tidak dapat melakukan hal yang sama dengan NFA? Saya tidak mencari bukti atau semacamnya - kecuali bukti lebih mudah dimengerti. Saya hanya ingin memahami secara intuitif mengapa minimalisasi NFA begitu sulit ketika minimisasi DFA tidak.

Untuk DFA ada struktur aljabar bagus yang menentukan negara mana yang bisa setara, kesetaraan Myhill-Nerode pada string terkait dengan minimalisasi DFA.

Untuk NFA situasinya rumit karena tidak ada NFA minimal yang unik secara umum.

Berikut adalah contoh untuk bahasa terbatas . Kedua automata keduanya state-minimal. Contohnya adalah dari makalah Catatan tentang automata minimal non-deterministik oleh Arnold, Dicky dan Nivat.$\{ ab, ac, bc, ba, ca, cb\}$

Jawaban ini mencoba mengungkapkan fakta bahwa kedua masalah itu "secara teknis" berbeda. Lihat jawaban oleh vzn untuk detail bagaimana masalah berbeda dalam kompleksitas komputasi.

Anda bertanya tentang pengambilan intuitif.

Dalam DFA, setiap awalan input yang diberikan hanya dapat mencapai paling banyak satu negara. Satu kemudian dapat menggabungkan pasangan negara yang tidak bisa dibedakan untuk sufiks apa pun. Negara yang dapat dibedakan oleh beberapa suffix tidak dapat digabungkan. Ini mengarah ke otomat minimal yang isomorfik untuk semua automata minimal lainnya.

$pq$$p$$P$$P$$q$$Q$$P$$q$$P$$Q$

$n$$2^n$

$O(ns \log n)$

lihat juga pertanyaan TCS.se ini menghitung NFA minimal untuk DFA