Library

EPDA · Tree-adjoining (mildly context-sensitive)

A copy, with a stack of stacks: w#w

One stack reverses w, which is useless for a copy. But popping it again, and parking each symbol on a stack of its own beneath the working one, reverses it a second time — so when the working stack runs out, the parked stacks come back in reading order, one per symbol of the copy.

q0readparkmatchdone
The machine as drawn — 5 states, 10 transitions.

The author’s examples, run

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