PDF logo Minimal DFA for testing divisibility

by Boris Alexeev


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.

Useful links

PDF logoDirect PDF link
Journal icon Published journal version
DOI icon Persistent document object identifier (DOI)
arXiv icon arXiv online preprint server version
MathSciNet icon Math Reviews (MathSciNet) review
Computing Reviews icon Computing Reviews review
Google Scholar icon Google Scholar entry
BiBTeX icon Individual BiBTex entry