DFA minimal yang memuaskan tampilan bahasa yang terbatas

Katakanlah seseorang memiliki bahasa , tetapi orang tidak tahu string apa yang sebenarnya bagian dari bahasa tersebut. Semua yang dimiliki adalah pandangan terbatas bahasa: seperangkat string terbatas A ⊆ L yang dikenal dalam bahasa tersebut, dan seperangkat string terbatas B ⊆ ( Σ ∗ ∖ L ) yang diketahui tidak berada dalam bahasa.$L \subseteq \Sigma^*$$A \subseteq L$$B \subseteq (\Sigma^* \setminus L)$

Sebagai contoh, katakanlah saya memiliki dan B = { b , a a b , a a a b a } . Saya mungkin memiliki bahasa L = { a 2 i + 1 b j | i , j ∈ N } , karena $A = \{ab, aaab, aaaaabb\}$$B = \{b, aab, aaaba\}$$L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$$A$dan $B$ konsisten dengan $L$ , atau saya mungkin memiliki bahasa yang sama sekali berbeda.

Pertanyaan saya adalah: apakah ada cara yang diketahui untuk membuat DFA (deterministic finite automata) yang menerima string dalam $A$ dan menolak string dalam $B$ , dengan jumlah minimal atau hampir-hampir minimal negara? Apa kerumitan masalah ini? Seberapa baik dalam mendekati $L$ (dengan asumsi $L$ memiliki kompleksitas deskriptif yang cukup rendah, dan $A$ dan $B$ besar)?

Pertanyaan asli di math.stackexchange.com. Saya memutuskan untuk mem-posting ulang di sini setelah tidak mendapatkan jawaban pada pertanyaan awal, dan tidak tahu ke mana harus mencari mereka. Jika seseorang dapat mengarahkan saya ke penelitian di bidang ini, itu akan sangat dihargai.

$\mathsf{NP}$$\mathsf{P}$

$W$$L_W$$G$$L_W$

$W$$G$$W$

$W$

• Batas bawah untuk belajar dalam kueri keanggotaan dan model kontra-contoh

• Apakah ada peningkatan pada algoritma Dana Angluin untuk mempelajari perangkat reguler

Sepertinya saya bahwa Anda dapat menggunakan penyempurnaan kesetaraan Myhill-Nerode untuk masalah ini.

x ∈ Σ u x ∈ A v x ∈ B A B u $u\nsim v$$x\in\Sigma$$ux\in A$$vx\in B$$A$$B$$u$$v$

Itu sudah cukup untuk mempelajari hubungan ini lebih prefiks dari unsur dan . Ini akan memberi Anda batas bawah pada jumlah negara yang Anda butuhkan. Saya tidak yakin itu secara langsung memberi Anda cara untuk membangun otomat minimal, tetapi setidaknya jalan untuk dijelajahi.$A$$B$

Saya pikir masalah ini mungkin secara tidak tepat diungkapkan oleh si penanya. Si penanya rupanya menginginkan algoritma yang menggeneralisasikan kata-kata tak terbatas berdasarkan contoh-contoh kata terbatas tertentu, dengan menggunakan semacam induksi mekanis, yaitu mengenali pola-pola nyata dalam contoh-contoh.

Selain beberapa penelitian teori CS yang dikutip dalam komentar, ada juga beberapa penelitian lebih empiris di bidang ini misalnya di bawah ini, menggunakan JST untuk membuat FSM dari contoh. Catatan satu selalu dapat menjalankan algoritma minimalisasi DFA standar pada hasilnya. Perpustakaan AT&T FSM baik untuk bekerja di area ini.

Penanya tidak spesifik tentang domain masalahnya, yang dapat membantu memahami struktur contoh dan mendapatkan referensi yang lebih spesifik. Namun, satu contoh yang dapat dilihat adalah algoritma AI dalam game yang menggunakan algoritma FSM. Saya menduga ada beberapa kasus di mana FSM dipelajari dari contoh menggunakan algoritma pembelajaran.

[1] Mempelajari kelas mesin negara berhingga besar dengan jaringan saraf berulang C. Lee Giles, 1, BG Horne, T. Lin 1995

[2] Mempelajari FSM dengan jaringan berulang pengelompokan mandiri oleh Zeng & Smyth 1993

[3] Perpustakaan AT&T FSM