Library

QA · Recursively enumerable

Is v a rotation of w? w#v

Enqueue w, then rotate: take the front symbol and put it at the back, as many times as the machine likes. Then check that v is what the queue holds. abc has rotations abc, bca and cab — a stack cannot rotate, a queue does it in one move.

loadspincheckwrapdone
The machine as drawn — 5 states, 12 transitions.

The author’s examples, run

# → acceptab#ba → accepta#a → acceptaabb#abba → accepta → rejectbb#ba → rejectb#a → rejectbabb#abba → reject