Library

Moore · Rational transduction

A three-bit linear-feedback shift register

Each tick t shifts the register and feeds back the XOR of two of its bits; the output is the bit shifted out. Seeded with 001 it runs through all seven non-zero states before repeating — a maximal-length sequence, the cheapest pseudo-random generator in hardware, and a Moore machine with one input letter.

s001s010s101s011s111s110s100ttttttt
The machine as drawn — 7 states, 7 transitions.

The author’s examples, run

t → reject · 00tt → reject · 001ttt → reject · 0010tttt → reject · 00101ttttt → reject · 001011tttttttttttttttt → reject · 00101110010111001