18
$\begingroup$

I'm working on a problem set for a class, and thought of a question related to what I was working on. Is there a minimum number of states that a finite automaton must have in order to accept binary strings that represent numbers divisible by an integer n? In an earlier problem set, I was able to construct a DFA that accepted binary strings divisible by 3 with 3 states. Is this a coincidence, or is there something inherent to the general problem of detecting strings divisible by n that suggests a minimum number of states?

I promise this will not answer a homework question for me! :)

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$
    – Kaveh
    Jan 29, 2012 at 4:09
  • 2
    $\begingroup$ @Kaveh: I think the question is okay, especially given David's concise answer. $\endgroup$
    – Huck Bennett
    Jan 29, 2012 at 5:27
  • 2
    $\begingroup$ @HuckBennett I agree with Kaveh that this question should be closed on cstheory, mostly to be consistent. However, I also agree with you: this is a fun question and when you first see DFAs it is definitely one you should be asking yourself. I think the OP should try to have some fun working out the answer for himself, and then consult math.SE for more info. $\endgroup$
    – Artem Kaznatcheev ♦
    Jan 29, 2012 at 6:10
  • 12
    $\begingroup$ This isn't homework (although it's inspired by a homework question), it's an interesting question, I don't believe it's a well-known result and the answer to the question appeared in a research journal. I don't see why it should be closed. The upper bound was homework, and is indeed easy, but the question was about the lower bound. $\endgroup$
    – Peter Shor
    Jan 29, 2012 at 13:43
  • 1
    $\begingroup$ @Janoma: Indeed. The end of the question suggests the OP confuses upper bounds with lower bounds. $\endgroup$
    – Michael Blondin
    Jan 29, 2012 at 22:55

2 Answers 2

Reset to default
32
$\begingroup$

There is a known formula for minimum number of states for such a finite automaton. This depends on $n$ as well as the radix $R$ of the underlying positional representation.

If $n$ is coprime to $R$, then the minimal number of states is $n$. However, when $n$ shares a factor with the radix then the situation is rather complicated. See Mathematica Journal Vol 3 Issue 11. "Divisibility and State Complexity" by Klaus Sutner.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Exactly the sort of thing I was looking for. Thanks, I'll dive into the paper sometime soon. $\endgroup$
    – Nick Van Hoogenstyn
    Jan 29, 2012 at 21:15
  • 2
    $\begingroup$ The link seems broken $\endgroup$
    – gigabytes
    Jul 27, 2016 at 12:47
9
$\begingroup$

There's another paper on the same subject: B. Alexeev, Minimal DFA for testing divisibility, J. Comput. Syst. Sci. 69 (2004), 235–243.

Improve this answer
$\endgroup$

Your Answer

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

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