Automata learning without counterexamples

Question

In Angluin's automata learning framework, a student aims to learn a regular language $L\subseteq \Sigma^*$ by asking two types of questions to his teacher:

Word queries: given $w\in \Sigma^*$, is $w\in L$?

Equivalence queries: given a language $K\subseteq \Sigma^*$, is $K=L$? If not, the teacher gives a counterexample, i.e. a word $w\in K\setminus L \cup L\setminus K$.

Using Angluin's algorithm, the student learns $L$ with polynomially many queries in the number of states of the minimal DFA of $L$ and the size of the counterexamples.

Now, consider a restricted scenario where the teacher no longer gives counterexamples. Is it still possible to learn L with a polynomial number of queries? I conjecture that this is not the case because for every polynomial-length sequence of queries and answers, one can find several regular languages consistent with the answers.

Does anyone see how to prove this?

Answer 1

Consider password automata: for each $w\in\{0,1\}^n$, the DFA $M_w$ accepts the language $\{w\}$. In this case, a membership query is the same as an equivalence query --- and clearly, you'll need exponentially many of these to find the "needle in the haystack". (This is even if the learner knows in advance that the target automaton is of this form.) For a formal proof, a teacher could simply respond to the first $2^{n}-1$ membership/equivalence queries with NO, adaptively choosing the target automaton as the unique remaining possibility.

Update. I neglected to mention that the password automaton has $n+1$ states and is learnable using a single standard Angluin equivalence query (namely, with candidate $M$ as the empty automaton).

Answer 2

Mark Gold indeed proved this very claim in his seminal paper "Language Identification in the Limit". This quite a well-known result now. You can find more on this in Colin de La Higuera's book on Grammatical Inference.