Library

DFA · Regular

Shuffling three cards

s swaps the top two cards; c moves the top card to the bottom. Accepted: the shuffles that put the deck back in order. The six states are the six orders, and the machine is the Cayley graph of the permutation group S₃.

ABCBACBCAACBCBACABscscscscscsc
The machine as drawn — 6 states, 12 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptccssc → acceptss → acceptcccccsscss → accepts → rejectscssc → rejectcs → rejectsccccsscss → reject