Belajar automata tanpa contoh tandingan

Dalam rangka belajar automata Angluin ini , sebuah tujuan siswa untuk belajar bahasa reguler $L\subseteq \Sigma^*$ dengan meminta dua jenis pertanyaan untuk gurunya:

Kueri kata: diberikan $w\in \Sigma^*$ , adalah$w\in L$ ?

Kueri kesetaraan: diberi bahasa $K\subseteq \Sigma^*$ , apakah $K=L$ ? Jika tidak, guru memberikan contoh yang menyangkal pernyataan, yaitu kata $w\in K\setminus L \cup L\setminus K$ .

Dengan menggunakan algoritma Angluin, siswa belajar $L$ dengan banyak pertanyaan secara polinomi dalam jumlah status DFA minimal $L$ dan ukuran sampel tandingan.

Sekarang, pertimbangkan skenario terbatas di mana guru tidak lagi memberikan contoh tandingan. Apakah masih mungkin untuk belajar L dengan jumlah kueri polinomial? Saya menduga bahwa ini tidak terjadi karena untuk setiap urutan panjang pertanyaan dan jawaban polinomial, kita dapat menemukan beberapa bahasa reguler yang konsisten dengan jawaban.

Adakah yang melihat bagaimana membuktikan ini?

$w\in\{0,1\}^n$$M_w$$\{w\}$$2^{n}-1$

$n+1$$M$

Mark Gold memang membuktikan klaim ini dalam makalah seminalnya "Identifikasi Bahasa dalam Batas". Ini hasil yang cukup terkenal sekarang. Anda dapat menemukan lebih banyak tentang hal ini dalam buku Colin de La Higuera tentang Grammatical Inference.