1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So I guess I should've tried the induction with reducing 3 stacks to 2, not 2 to 1. Thanks! $\endgroup$ – Joshua Apr 28 '18 at 21:22
  • $\begingroup$ 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). $\endgroup$ – narek Bojikian Nov 7 '19 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.