Library

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”.

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

The author’s examples, run

# → acceptab#ab → acceptbaa#baa → acceptbabba#babba → accepta → rejectbb#ab → rejectaaa#baa → rejectaabba#babba → reject