Library

DFA · Regular

A knight on a 3 × 3 board

Starting in a corner, the knight moves in any of its eight directions (A–H) without leaving the board. The centre is unreachable, and the other eight squares form a single ring, each joined to the two squares a knight’s move away. So a closed tour has even length, and going once round the ring takes eight moves.

a3c2b1a1c3b3a2c1CDFGAHABEFDEBCGH
The machine as drawn — 8 states, 16 transitions.

The author’s examples, run

ε → acceptCG → acceptDH → acceptA → rejectAG → rejectAH → rejectBCEDHEGF → reject