<p>The last step of the proposed reasoning can be done as described in <a href="https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain">https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain</a> and in <a href="https://cs.stackexchange.com/questions/92496/proving-that-dfa-equivalence-is-decidable">https://cs.stackexchange.com/questions/92496/proving-that-dfa-equivalence-is-decidable</a>. Hence, if <span class="math-container">$n$</span> states allowed, then all strings of length <span class="math-container">$n^2$</span> can be checked in the black-box DFA to discard all non-equivalent DFAs, and then we can take the smallest non-discarded DFA.</p>

CC BY-SA 4.0
2024-01-10T00:17:23.743Z
2024-01-10T00:17:23.743Z
EXPTIME-complete
<p>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 <a href="https://cstheory.stackexchange.com/questions/37595/number-of-minimal-dfas-of-size-at-most-m">finite number of such DFAs</a>, 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?</p>

CC BY-SA 4.0
2024-01-09T17:13:21.353Z
Maybe you are trying to solve the same problems as in https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain or as in https://cs.stackexchange.com/questions/92496/proving-that-dfa-equivalence-is-decidable, right?
EXPTIME-complete
CC BY-SA 4.0
2024-01-09T17:21:21.107Z
(At least, in the last part of your reasoning).
EXPTIME-complete
CC BY-SA 4.0
2024-01-09T17:47:34.337Z
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.
EXPTIME-complete
CC BY-SA 4.0
2024-01-09T21:57:05.927Z
@EXPTIME-complete Yes, thank you, the links are indeed very relevant, and as you observed, sufficient to answer my question. Thanks again.
Rahul Gopinath
<automata-theory><lg.learning><regular-language><dfa>
What is the current state of the art on exact identification of DFAs with a maximum N states
Rahul Gopinath
# What is the current state of the art on exact identification of DFAs with a maximum N states

(Asked by: username_0 on 2024-01-08)

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](https://cstheory.stackexchange.com/questions/37595/number-of-minimal-dfas-of-size-at-most-m), 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?

**Tags:** automata-theory, lg.learning, regular-language, dfa
> **Comments:**
> **username_1**: Maybe you are trying to solve the same problems as in https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain or as in https://cs.stackexchange.com/questions/92496/proving-that-dfa-equivalence-is-decidable, right?  
> **username_1**: (At least, in the last part of your reasoning).  
> **username_1**: 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.  
> **username_0**: @EXPTIME-complete Yes, thank you, the links are indeed very relevant, and as you observed, sufficient to answer my question. Thanks again.  

---

## 1 answers

### Answer by username_1 on 2024-01-10. Score: 2 | Accepted answer

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.


---

