Library

EPDA · Tree-adjoining (mildly context-sensitive)

aⁿbⁿcⁿdⁿ — four counts, one stack of stacks

Two independent stacks would be Turing power; one stack whose elements are stacks is exactly enough. The a's and b's are matched on the working stack while the c's and d's are parked beneath it, to be picked up in order once it is gone.

startcount amatch bmatch cmatch ddone
The machine as drawn — 6 states, 9 transitions.

The author’s examples, run

abcd → acceptaabbccdd → acceptaaabbbcccddd → acceptaabbcd → rejectabccdd → rejectabcdd → rejectaabbccd → rejectabdc → reject