Smallest automaton for multiples of six
A deterministic finite automaton reads a binary string most-significant bit first and must accept exactly the strings whose value is divisible by 6 (leading zeros allowed; treat the empty string as the number 0, so it is accepted). What is the minimum number of states such a DFA needs?
Show hints (3)+
- Appending bit turns value into ; track .
- Look for residues whose transition rows are identical.
- Refine the partition {accepting} vs {rest} until it stabilises.
Answer
Reveal answer →Final answer
4
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading