DFA — decimal, divisible by 3
Decimal numerals whose value is divisible by 3.
Residue-class construction
Input
Narration
Start in state r0 with "12" still to read.
Deterministic finite automatonHopcroft 2e §2.2 — δ̂
Exactly one move per state and symbol, so a run is a single path. The string is accepted if that path ends in an accepting state.
This machine3 states
- Q
- {r0, r1, r2}
- Σ
- {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- q₀
- r0
- F
- {r0}
- |δ|
- 30 transitions
How to read the run
- One state is current at a time; it is outlined in blue.
- The transition just taken is drawn in blue, and the symbol just read is boxed.
- If a state has no move on the next symbol, the run dies there and the string is rejected — that is the implicit dead state a textbook diagram leaves off.
Run many strings
One string per line. A blank line means the empty string.