Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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 4:09
2  
@Kaveh: I think the question is okay, especially given David's concise answer. –  Huck Bennett Jan 29 '12 at 5: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 6:10
11  
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
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

1 Answer 1

up vote 26 down vote accepted

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.

share|improve this answer
1  
Exactly the sort of thing I was looking for. Thanks, I'll dive into the paper sometime soon. –  Nick Van Hoogenstyn Jan 29 '12 at 21:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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