Automatyczne uczenie się bez kontrprób

W programie do nauki automatów Angluin , uczeń chce nauczyć się zwykłego języka , zadając swojemu nauczycielowi dwa rodzaje pytań:$L\subseteq \Sigma^*$

Zapytania słowne: biorąc pod uwagę , czy ?$w\in \Sigma^*$$w\in L$

Zapytania o równoważność: biorąc pod uwagę język , czy ? Jeśli nie, nauczyciel daje kontrprzykład, to słowo .$K\subseteq \Sigma^*$$K=L$$w\in K\setminus L \cup L\setminus K$

Korzystając z algorytmu Angluina, uczeń uczy się z wielomianowo wieloma zapytaniami o liczbę stanów minimalnego DFA i wielkość kontrprzykładów.$L$$L$

Rozważmy teraz ograniczony scenariusz, w którym nauczyciel nie daje już kontrpróbek. Czy nadal można nauczyć się L z wielomianową liczbą zapytań? Przypuszczam, że tak nie jest, ponieważ dla każdej wielomianowej sekwencji zapytań i odpowiedzi można znaleźć kilka zwykłych języków zgodnych z odpowiedziami.

Czy ktoś widzi, jak to udowodnić?

Rozważ automaty haseł : dla każdego , DFA akceptuje język . W takim przypadku zapytanie o członkostwo jest takie samo, jak zapytanie o równoważność --- i oczywiście potrzeba ich wykładniczo wielu z nich, aby znaleźć „igłę w stogu siana”. (Dzieje się tak nawet wtedy, gdy uczący się z góry wie, że automat docelowy ma taką postać.) W celu uzyskania formalnego dowodu nauczyciel może po prostu odpowiedzieć na pierwsze zapytań o członkostwo / równoważność NIE, wybierając odpowiednio automat docelowy jako jedyna pozostała możliwość.$w\in\{0,1\}^n$$M_w$$\{w\}$$2^{n}-1$

Aktualizacja. Zlekceważyłem wspomnieć, że automat haseł ma stany i można się go nauczyć za pomocą pojedynczego standardowego zapytania równoważności Angluin (mianowicie z kandydatem jako pustym automatem).$n+1$$M$

Mark Gold rzeczywiście udowodnił to twierdzenie w swoim przełomowym artykule „Language Identification in the Limit”. To dość dobrze znany wynik. Więcej na ten temat można znaleźć w książce Colina de La Higuery na temat wnioskowania gramatycznego.