Question

5 How Many Stacks?

An NFA has no stack. It recognizes regular languages.

A PDA is defined as an NFA with one stack. It recognizes context-free languages.

Prove that a PDA with two stacks recognizes Turing-recognizable languages

Answer 1

A PDA with two-stack is powerful as a Turing Machine. It's simple to assume that we are using the model of TMs that has a tape that's one direction infinite only.

To see the equivalence, just think of the first stack consists of the contents of the tape to the left of the current position, and the second as the contents to the right. You will begin like :

Push the normal "bottom of stack" marks on both stacks.

Push the input to the left stack (use non-determinism to "guess" the end of the input).

Move everything to the right stack (to keep things in the proper order).

Now you can reject the input and do everything on the contents of the stacks . You pop to read and push to write (so you can change the "tape" by pushing something different to what you read). Then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.