<p>Consider <em>password</em> automata: for each <span class="math-container">$w\in\{0,1\}^n$</span>, the DFA <span class="math-container">$M_w$</span> accepts the language <span class="math-container">$\{w\}$</span>. 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 <span class="math-container">$2^{n}-1$</span> membership/equivalence queries with NO, adaptively choosing the target automaton as the unique remaining possibility.</p>

<p>Update. I neglected to mention that the password automaton has <span class="math-container">$n+1$</span> states and is learnable using a single standard Angluin equivalence query (namely, with candidate <span class="math-container">$M$</span> as the empty automaton).</p>

CC BY-SA 4.0
2018-10-24T13:23:19.803Z
2018-10-31T15:17:14.283Z
2018-10-31T15:17:14.283Z
Aryeh
<p>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.</p>

CC BY-SA 4.0
2019-02-12T22:09:08.520Z
2019-02-12T22:09:08.520Z
Roman Manevich
<p>In <a href="https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/papers/angluin87.pdf" rel="noreferrer">Angluin's automata learning framework</a>, a student aims to learn a regular language <span class="math-container">$L\subseteq \Sigma^*$</span> by asking two types of questions to his teacher:</p>

<p>Word queries: given <span class="math-container">$w\in \Sigma^*$</span>, is <span class="math-container">$w\in L$</span>?</p>

<p>Equivalence queries: given a language <span class="math-container">$K\subseteq \Sigma^*$</span>, is <span class="math-container">$K=L$</span>? If not, the teacher gives a counterexample, i.e. a word <span class="math-container">$w\in K\setminus L \cup L\setminus K$</span>.</p>

<p>Using Angluin's algorithm, the student learns <span class="math-container">$L$</span> with polynomially many queries in the number of states of the minimal DFA of <span class="math-container">$L$</span> and the size of the counterexamples.</p>

<p>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. </p>

<p>Does anyone see how to prove this?</p>

<automata-theory><regular-language>
Automata learning without counterexamples
user49692
# Automata learning without counterexamples

(Asked by: username_0 on 2018-10-24)

In [Angluin's automata learning framework](https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/papers/angluin87.pdf), 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?

**Tags:** automata-theory, regular-language


---

## 2 answers

### Answer by username_1 on 2018-10-24. Score: 20

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 by username_2 on 2019-02-12. Score: 1

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.


---

