2PDA · Recursively enumerable
Two stacks make a queue: w#w
One stack reverses, so two stacks reverse twice: push w on the first, pour it onto the second, and the second now holds w in reading order, ready to match the copy. The trick behind “two stacks are as strong as a Turing machine”.
The author’s examples, run
# → acceptab#ab → acceptbaa#baa → acceptbabba#babba → accepta → rejectbb#ab → rejectaaa#baa → rejectaabba#babba → reject