Skip to content
Get started

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)+
  1. Appending bit bb turns value xx into 2x+b2x + b; track x mod 6x \bmod 6.
  2. Look for residues whose transition rows are identical.
  3. Refine the partition {accepting} vs {rest} until it stabilises.

Answer

Reveal answer →

4

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions