Library

Mealy · Rational transduction

Times three, serially

Multiply a binary number by 3 as it streams in, least significant bit first. 3n = 2n + n, so each output bit is the input bit plus the previous one plus a carry; the carry can reach 2, so the states are the carries 0, 1 and 2 together with the last bit read. Feed enough trailing zeros to flush the carry.

c0_0c0_1c1_1c1_0c2_0c2_10/01/10/11/00/11/00/01/10/01/10/11/0
The machine as drawn — 6 states, 12 transitions.

The author’s examples, run

0 → reject · 01 → reject · 100 → reject · 0001 → reject · 01000 → reject · 0001111101100011000 → reject · 1011100101010010