Library

QA · Recursively enumerable

Three copies: w#w#w

A queue can check a copy without losing it: while matching the second w, each symbol taken from the front is sent straight to the back again, ready for the third. A stack would have to give up what it compares.

loadcopylastdone
The machine as drawn — 4 states, 9 transitions.

The author’s examples, run

## → acceptab#ab#ab → acceptbba#bba#bba → acceptabab#abab#abab → accepta# → rejectbb#ab#ab → rejectaba#bba#bba → rejectbbab#abab#abab → reject