DFA terkecil yang menerima string yang diberikan dan menolak string yang diberikan lainnya

11

Diberikan dua set SEBUAH,B string lebih dari alfabet Σ , dapatkah kita menghitung otomat kondisi-terbatas deterministik terkecil (DFA) M. sehingga SEBUAH⊆L.(M.) dan L.(M.)⊆Σ∗∖B ?

Dengan kata lain, mewakili sekumpulan contoh positif. Setiap string dalam A harus diterima oleh DFA. B mewakili sekumpulan contoh negatif. Tidak ada string dalam B yang harus diterima oleh DFA.SEBUAHSEBUAHBB

Apakah ada cara untuk mengatasi ini, mungkin menggunakan teknik minimalisasi DFA ? Saya bisa membayangkan membuat otomat seperti DFA yang memiliki tiga jenis negara: menerima negara, menolak negara, dan negara "tidak peduli" (input yang berakhir di negara "tidak peduli" dapat diterima atau ditolak). Tetapi bisakah kita menemukan cara untuk meminimalkan ini ke DFA biasa?

Anda dapat menganggap ini sebagai masalah mempelajari DFA, dengan memberikan contoh positif dan negatif.

Ini terinspirasi oleh Apakah golf regex NP-Complete? , yang menanyakan pertanyaan serupa untuk regexps dan bukan DFA.

regular-languages automata finite-automata machine-learning DW
sumber
1
Saya pikir Anda harus memberi semacam batasan pada bahasa apa dan B mungkin dan bagaimana mereka ditentukan. SEBUAHB
reinierpost
Ada banyak literatur tentang fungsi / bahasa pembelajaran, misalnya diajukan dalam batas belajar (juga pembelajaran gaya Emas). Ini tidak sesuai dengan masalah Anda, tetapi mungkin menarik.
Raphael

Jawaban:

7

DFA seperti yang Anda gambarkan disebut DFA pemisah . Ada beberapa literatur tentang masalah ini ketika SEBUAH dan adalah bahasa reguler, seperti Learning Minimal Separating DFA's for Compositional Verification, oleh Yu-Fang Chen, Azadeh Farzan, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw WangB

Perhatikan bahwa sebagai @reinierpost menyatakan, tanpa batasan pada A dan B, masalahnya mungkin menjadi tidak dapat ditentukan.

Shaull
sumber
Jika A dan B keduanya bahasa biasa, dan jika seseorang diizinkan untuk secara sewenang-wenang menerima atau menolak input yang mana A dan B akan menghasilkan hasil yang sama, saya tidak melihat bagaimana masalahnya bisa diputuskan. Untuk DFA dengan ukuran tertentu, akan mungkin untuk membangun satu set input lengkap yang harus diterima dan input yang harus ditolak, sehingga setiap DFA dengan jumlah status yang sama atau lebih sedikit yang menangani dengan benar semua kasus uji dapat dijamin berperilaku identik dalam semua kasus. Karena mesin yang menerima segalanya A menerima dan menolak yang lainnya akan ...
supercat
... memenuhi batasan, seseorang dapat menempatkan batas atas pada jumlah kondisi yang harus dikandung mesin; karena ada sejumlah mesin yang memungkinkan dengan ukuran tertentu, dan sejumlah kasus uji untuk dievaluasi, orang dapat menghasilkan semua mesin yang mungkin lebih kecil dari A dan melihat apakah ada di antara mereka yang memenuhi persyaratan yang diperlukan. Bukan cara yang cepat untuk menyelesaikan masalah, tetapi tentu saja dapat diperhitungkan jika A dan B teratur. Jika mereka tidak teratur, DFA tidak akan dapat menyelesaikan A atau B. "Perbedaan" kadang-kadang mungkin teratur bahkan jika A dan B tidak, tapi itu ...
supercat
... akan menjadi kasus "tidak biasa".
supercat
8

Ada banyak literatur tentang pembelajaran DFA yang diberikan sampel positif dan negatif. Jika dan B terbatas, saya tidak melihat bagaimana masalah akan diputuskan. Jika A ∩ B = ∅ maka jelas DFA yang hanya menerima string dalam A memenuhi kebutuhan Anda dan satu dapat dengan mudah menyebutkan semua DFA yang lebih kecil. Jika A ∩ B ≠ ∅ maka jelas tidak ada DFA tersebut.SEBUAHBSEBUAH∩B=∅SEBUAHSEBUAH∩B≠∅

Menemukan DFA minimum yang konsisten dengan serangkaian string yang diberikan adalah NP-complete. Hasil ini muncul sebagai Teorema 1 di kertas Angluin Pada kompleksitas inferensi minimum dari set reguler . Jadi jelas masalah Anda juga NP-complete.

Untuk banyak tautan dan diskusi yang baik tentang belajar bahasa reguler, lihat blog post CSTheory On Learning Regular Languages .

alto
sumber
Jika persyaratan diubah sehingga otomaton dapat secara sewenang-wenang menerima atau menolak apa pun yang ada dalam A dan B, maka masalahnya akan selalu dapat dipecahkan untuk A dan B; jika menemukan automaton yang optimal akan menjadi NP-lengkap tanpa melakukan itu, itu akan menjadi NP-complete bahkan dengan persyaratan itu.
supercat