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.

Useful links

	Direct PDF link
	Published journal version
	Persistent document object identifier (DOI)
	arXiv online preprint server version