Library

Mealy · Rational transduction

Dividing by 3, most significant bit first

Long division in binary, one bit at a time. The state is the remainder so far; reading bit b makes it 2r + b, and the quotient bit printed is whether that reached 3. The same three states as the divisibility DFA — which only kept the remainder and threw the quotient away.

r0r1r20/01/00/01/10/11/1
The machine as drawn — 3 states, 6 transitions.

The author’s examples, run

0 → reject · 01 → reject · 000 → reject · 0001 → reject · 00000 → reject · 0001111101100011000 → reject · 0101001110110010