This is a question about the blackbox grammar inference of deterministic finite state automata (DFAs). In particular I want to ask about when one can exactly identify the target DFA using queries to the oracle. I understand that exact identification of target DFA (where the DFA learned is exactly the same as the target DFA for learning) is only possible in the limit, and that too only with the aid of a MAT (a Minimally Adequate Teacher able to answer equivalence queries, and provide counter examples if the hypothesis DFA is different from the target), intuitively it seems that exact identification of minimal DFAs should be possible even with out a MAT if there is a constraint on the number of states possible in the minimal DFA. My reasoning is that there is a finite number of such DFAs, and distinguishing between any two DFAs of a finite number of states should be doable with a finite size string. Is my intuition correct? Is this question discussed anywhere?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Maybe you are trying to solve the same problems as in cs.stackexchange.com/questions/48136/… or as in cs.stackexchange.com/questions/92496/…, right? $\endgroup$– EXPTIME-completeCommented Jan 9 at 17:13
-
$\begingroup$ (At least, in the last part of your reasoning). $\endgroup$– EXPTIME-completeCommented Jan 9 at 17:21
-
$\begingroup$ And having that step, the rest is trivial: if the maximum number of states is assumed to be n, then apply all n^2-length strings to distinguish the unknown target DFA from all other non-equivalent candidate DFAs having up to n states. Finally, in the set of equivalent candidate DFAs, pick the one having less states. $\endgroup$– EXPTIME-completeCommented Jan 9 at 17:47
-
$\begingroup$ @EXPTIME-complete Yes, thank you, the links are indeed very relevant, and as you observed, sufficient to answer my question. Thanks again. $\endgroup$– Rahul GopinathCommented Jan 9 at 21:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The last step of the proposed reasoning can be done as described in https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain and in https://cs.stackexchange.com/questions/92496/proving-that-dfa-equivalence-is-decidable. Hence, if $n$ states allowed, then all strings of length $n^2$ can be checked in the black-box DFA to discard all non-equivalent DFAs, and then we can take the smallest non-discarded DFA.
