In our CS class, we have a question about the computational power of PDA's (Push Down Automaton). A 0-PDA (PDA with no stacks) is equivalent to an NFA (Non-deteministic Finite Automaton), while a 1-PDA (the standard PDA) is equivalent to a CFG (Context Free Grammar).
However, a 2-PDA (PDA with 2 stacks) is more powerful (recognises more languages) than a 1-PDA, because it is not limited to pushing and popping on 1 stack only, but can also use the second stack.
The problem that I have is that I don't know how to prove the greater power of the 2-PDA. My first thought was that a 2-PDA would be equivalent to a Turing Machine, but then I realised that it still wouldn't quite provide arbitrary access to the stack.
How would I go about proving that a 2-PDA is more powerful than a 1-PDA?
(Could someone with enough rep please tag this as homeworkpda - thanks)