Editing Pushdown automaton (section)

==Turing machines==

A pushdown automaton is computationally equivalent to a "restricted" Turing Machine (TM) with two tapes which is restricted in the following manner- On the first tape, the TM can only read the input and move from left to right (it cannot make changes). On the second tape, it can only "push" and "pop" data. Or equivalently, it can read, write and move left and right with the restriction that the only action it can perform at each step is to either delete the left-most character in the string (pop) or add an extra character left to the left-most character in the string (push).

That a PDA is weaker than a TM can be brought down to the fact that the procedure "pop" deletes some data. In order to make a PDA as strong as a TM, we need to save somewhere the data lost through "pop". We can achieve this by introducing a second stack. In the TM model of PDA of last paragraph, this is equivalent to a TM with 3 tapes, where the first tape is the read-only input tape, and the 2nd and the 3rd tape are the "push and pop" (stack) tapes. In order for such a PDA to simulate any given TM, we give the input of the PDA to the first tape, while keeping both the stacks empty. It then goes on to push all the input from the input tape to the first stack. When the entire input is transferred to the 1st stack, now we proceed like a normal TM, where moving right on the tape is the same as popping a symbol from the 1st stack and pushing a (possibly updated) symbol into the second stack, and moving left corresponds to popping a symbol from the 2nd stack and pushing a (possibly updated) symbol into the first stack. We hence have a PDA with 2 stacks that can simulate any TM.