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.
The author’s examples, run
# → acceptab#ba → accepta#a → acceptaabb#abba → accepta → rejectbb#ba → rejectb#a → rejectbabb#abba → reject