Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular language -- can we still learn a small DFA that approximates the target concept well?

Here's the formal setting. We have a target concept $f^\star$ and distribution $D$ over $\Sigma^*$. A membership query $MQ:\Sigma^*\to\{0,1\}$ returns the value of $f^\star(x)$. An "accuracy query" $AQ$ takes a DFA $f$ as input and returns $$\mathrm{err}(f):=\sum_{x\in\Sigma^*}D(x)\boldsymbol{1}[f(x)\neq f^\star(x)]$$ a output.

The goal is to efficiently produce a small (up to $n$-states) DFA $f$ with small (or minimum) $\mathrm{err}(f)$ using the oracles $MQ$ and $AQ$. [A trivial solution is to brute-force search over all $n$-state DFAs.]

Have similar problems been considered in the literature? Pointers much appreciated. What is the status of the learning problem I posed?

Edit: It was pointed out off-line that for parity-type concepts, $\mathrm{err}(f)$ might be close to $1/2$. So to clarify: the question seeks not a bound on the worst-case $\mathrm{err}(f)$, but rather an efficient procedure of attaining it via an $n$-state DFA.

  • $\begingroup$ So, if you allow an extra slack of say $\\varepsilon$ (and high probability of success only, instead of probability one), you can always cheaply estimate $\mathrm{err}(f)$ by sampling, and this becomes equivalent to proper PAC-learning DFAs with membership queries, isn't it? $\endgroup$
    – Clement C.
    Commented May 28, 2019 at 17:52
  • $\begingroup$ Yes, exactly right. I haven't yet figured out if this question and answer have any relevance cstheory.stackexchange.com/questions/153/… $\endgroup$
    – Aryeh
    Commented May 28, 2019 at 17:55
  • $\begingroup$ For the agnostic case, where $f^\ast$ may not itself be a DFA, this looks relevant (if I parse the abstract correctly: MQ are not very useful): jmlr.org/papers/volume10/feldman09a/feldman09a.pdf $\endgroup$
    – Clement C.
    Commented May 28, 2019 at 17:56
  • $\begingroup$ Hmm, you may be right. If you turn this into a full answer, I'll accept. $\endgroup$
    – Aryeh
    Commented May 28, 2019 at 18:00
  • $\begingroup$ That still leaves the non-agnostic case open, though (not sure how much of your original motivation that is). $\endgroup$
    – Clement C.
    Commented May 28, 2019 at 18:01

1 Answer 1


As mentioned in the comments, if you allow some extra additive slack of $\varepsilon\in(0,1]$ (an input parameter) in the error guarantee, and relax the success probability from one to $1-\delta$ (another input parameter), then the question becomes equivalent to agnostic PAC-learning the class $\mathcal{C}_n$ of $n$-state DFAs with membership queries.

Indeed, while you do not have accuracy queries $\mathrm{AQ}$, those can be easily simulated by sampling in the PAC setting (leading to the $\pm\varepsilon$ and $1-\delta$ relaxation).

However, this paper by Vitaly Feldman [Feldman09] shows that then, one may as well forget about the membership queries and focus on honest-to-goodness agnostic PAC learning:

[...] we give a simple proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries.

In this light, provided you are willing to proceed with the error slack and high-probability guarantee, then your question boils down to agnostic PAC learning of $n$-state DFAs.

[Feldman09] Vitaly Feldman. On The Power of Membership Queries in Agnostic Learning. Journal of Machine Learning Research (JMLR) 10(Feb):163--182, 2009.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.