< prev | up | next >

# Minimal DFA for testing divisibility

## by Boris Alexeev

### Abstract

We present and prove a theorem answering the question "how many states does a minimal deterministic finite automaton (DFA) that recognizes the set of base-$$b$$ numbers divisible by $$k$$ have?"

### Approximate citation

Boris Alexeev
Minimal DFA for testing divisibility
Journal of Computer and System Sciences 69 (2004), no. 2, 235–243.