# Simulate $n$-PDA with $n-1$-PDA

I've heard that every $n$-PDA when $n > 2$ is as powerful as $2$-PDA. Unfortunately every proof I'm able to find uses references to Turing Machines, which I haven't learned about yet. I'm sure there must exist an alternative proof, supposedly one that converts $n$-PDA to $n-1$-PDA, and then proceeds by induction, but I'm unable to find it. Any references, or hints are greatly appreciated.

What I tried: to simulate two stacks using just one, therefore going from $n$ to $n-1$. But it would also mean that $2$-PDA are as powerful as $1$-PDA, so it's clearly a wrong way.

Yes, any PDA with $n>2$ stacks can be simulated by a pda with $2$ stacks. It is possible to show this without explicitly using Turing machines.

Assume that you have $n$ stacks, with contents $\alpha_1$ to $\alpha_n$. Store all these stacks on top of each other, with special separator symbols $\square_i$. So a single stack contains $\square_1\alpha_1 \dots \square_n\alpha_n$ (top left). Now assume that I want to perform an operation on stack $k$ (look at the top, check it is empty, push or pop symbols). In order to do this use the second stack. Move all stacks up to the $k$th to the second stack (popping from the one pushing to the other). The two stacks are now $\square_1\alpha_1 \dots \square_k\alpha_k$ and $\alpha^R_n\square_n\dots \alpha^R_{k+1}\square_{k+1}$. it is now easy to operate on stack $k$ (since it is on top of one of the stacks). and in general we continue moving the $n$ stacks around between the two stacks to continue the simulation.

• So I guess I should've tried the induction with reducing 3 stacks to 2, not 2 to 1. Thanks! – Joshua Apr 28 '18 at 21:22
• It might worth mentioning that you can use the state to keep the letter on top of each stack while storing the contents on a different stack since you have constant number of stacks. Hence, you can do operations that need looking up more than one stack (at the same time). – narek Bojikian Nov 7 '19 at 22:53