18

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! :)

Nick Van Hoogenstyn
  • 309
  • 2
  • 6
  • The typical construction is easily generalized to $n$ states for mod $n$. It will all make sense when you'll understand why your DFA actually accepts the correct language. – Michael Blondin Jan 29 '12 at 02:15
  • 3
    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. – Kaveh Jan 29 '12 at 04:09
  • 2
    @Kaveh: I think the question is okay, especially given David's concise answer. – Huck Bennett Jan 29 '12 at 05:27
  • 2
    @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. – Artem Kaznatcheev Jan 29 '12 at 06:10
  • @ArtemKaznatcheev: Well put. Fair enough. – Huck Bennett Jan 29 '12 at 06:15
  • 12
    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. – Peter Shor Jan 29 '12 at 13:43
  • @MichaelBlondin that's true when the input is a number in unary notation. For example, in base 10, numbers divisible by 5 end in 0 or 5, so you only need two states for a DFA to accept them. – Janoma Jan 29 '12 at 13:47
  • 1
    @Janoma: Indeed. The end of the question suggests the OP confuses upper bounds with lower bounds. – Michael Blondin Jan 29 '12 at 22:55
  • suggest the moderator(s) not be so fast to kill questions (esp unilaterally) that come from site newbies or undergraduates & rely more on the built-in voting mechanisms instead. arguably this problem relates to the complexity of integer division, integer remainder, primality testing, factoring, gcd etc (lower bounds on which are mostly deep open questions) – vzn Jan 31 '12 at 21:33
  • here is an example of a deep link between regular languages, integer division, and a premiere open problem in math/CS, the collatz conjecture: Jeffrey O. Shallit and David W. Wilson (1991), The “3x + 1” Problem and Finite Automata, Bulletin of the EATCS (European Association for Theoretical Computer Science), No. 46, 1991, pp. 182–185. – vzn Feb 01 '12 at 16:46
  • but this question could also be construed to be asking about DFA minimization which is also a well studied problem see eg how do you normalize/minimize a FSM – vzn Feb 03 '12 at 16:35

2 Answers2

32

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.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
David Harris
  • 3,488
  • 22
  • 24
9

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

Jeffrey Shallit
  • 6,986
  • 33
  • 38