Minsky's Theorem
A two-pushdown stack machine, abbr. 2PDA, is a PDA with two pushdown stacks, the \tt PUSH and \tt POP operations must specify which stack they operate on, and 2PDA is deterministic.
2PDAs can actually accept some non-context-free langauges, for example, the following 2PDA acceptes old friend a^nb^na^n, it can be achieved by putting the three clusters of a and b into two stacks alternately
Turing equivalency
2PDA=TM
Proof
Let P be a 2PDA, The core idea of this proof is to flatten the three storage of P into a single storage, which is the tape of the TM, at first, we put all the contents on the input tape of P to the tape of TM T, then insert a \Delta at the very beginning of the tape of T, every time P reads a letter, we replace the corresponding letter to \Delta on the T's tape to simulates a consumption. We'll put a \# at the end of the content on T's tape, which is the end of the input string, it'll be considered as a base pointer, no matter how the tape head moves, it must return to the \# after finitely many steps before begin its next operation.
For a \tt READ operation on the P with three outgoing edges lead to states X, Y and Z each of which labeled with a, b and \Delta respectively, we do the following operations on the T to simulate it:
- Find the first non-\Delta character on the tape, since we've inserted a \Delta before machine starts this would be easy by using the algorithm we've frequently employed
- If the first non-\Delta character is \#, then the input string has been exhausted, we go to state Z because the state Z stands for a \Delta edge
- Otherwise, replace that letter with \Delta and head the tape head to the left, to prevent hitting the \# marker
- Go to the proper state decided by the character we've just read, then reset the tape head back to \#
The two stacks' content will appears from the left to right separated by \text{\textdollar} after the \#, for a \tt POP_1 state with three edges lead to X, Y and Z each of which labeled with a, b and \Delta respectively, we do the following to simulate it:
- Move the tape head to the right, if we meet \text{\textdollar} then the \tt STACK_1 must be empty, we write \text{\textdollar} and head the tape head to left, then we go to state Z since it's marked with \Delta and reset the tape head
- Otherwise we go to the proper state that decided by the character we read, then delete the character we read and reset the tape head(\tt DELETE is a subprogram can be implemented by TM)
To simulate a \tt PUSH_1\text{ x} state, just call the \tt INSERT\text{ x} and then reset the tape head
The \tt PUSH_2 and \tt POP_2 is very similar, just move the tape head to \text{\textdollar} then do exactly the same thing as to the \tt PUSH_1 and \tt POP_1
When the P reaches an \tt ACCEPT, we \tt HALT the TM T
To show the second part, which is that prove every langauge accepted by a TM can be accepted by some 2PDA, we do a simple exchange, let's prove that every langauge accepted by a PM can be accepted by some 2PDA, since we've proved that PM=TM, so this could also prove that 2PDA=TM. Firstly, we transfer all the contents on the input tape of P to its \tt STACK_1 while maintaining the same order, we can do this by put them in \tt STACK_2 first, which will reverse the order of input string, then pop them from \tt STACK_2 and pushes back to \tt STACK_1, now we need to simulate two operations of the PM, \tt ADD and \tt READ, the \tt READ operation is same as the \tt POP_1 operation on P since both of them remove the character at the very beginning at the input string then branching accordingly, the \tt ADD\text{ x} state, on the other hand, is a bit tricky, we need to empty \tt STACK_1 to \tt STACK_2 first, the push x to the \tt STACK_1, then we pop all the contents in \tt STACK_2 and push the back to the \tt STACK_1, this make the x becomes the bottommost element which is just like the rightmost element on the \tt STORE of the PM, while keep the order of other characters in the \tt STACK_1, since the PMs contain only these two operations, we can consider we've successfully simulated a 2PDA on PM, from the first and second part of this proof, we have 2PDA=TM
ocean liner.
n-Stack PDA
A PDA with n-Stacks is equivalent with 2PDA, in other words, nPDA=TM
Proof
There will be no even more powerful machines can be constructed by simply adding more stacks, the proof is very simple, for PDA with n stack, we separate the tape of the TM into n+2 sections, where the first section is the contents on the input tape of nPDA, the following n+1 sections represent the n stacks of the nPDA, and then the last section is filled with blanks, it is obvious that we can build such a machine by repeating the algorithm in the previous proof.
Comments | NOTHING