[Solved]: How exactly does a two stack pushdown automaton work?

Problem Detail: 

I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \{w\$w\ |\ w ∈ \{0,1\}^n\ with\ n>0\}$. So far, so good.

Now I know that a 2-PDA works with two stacks and is equivalent to a Turing Machine. It reads from an input tape and can save the current digit in either the first or the second stack. How can I decide in which stack the digit is read and/or saved? Especially since it's a computer program that should deal with that step.

Since it's equivalent to a Turing Machine, I get that one stack can deal with the left side and the other with the right side of the input. However, this is not really enough information for me to write a programm that simulates it. So how does the 2-PDA read the word, for instance, 01001$01001 from language $L$. Where does it begin? How does it accept the word?

I know, so many questions, I don't want to have them answered all in much detail but the most important thing is just how it works.

Asked By : Tim Wagner

Answered By : André Souza Lemos

To write a program that simulates a 2-PDA (which will be able to process any transition function $\delta$, not just a particular language) what you need to do is to implement a stack class, with just the operations that it is allowed to have. The simulator is essentially a loop that keeps track of the current state of $\delta$, which has to be stored in a suitable way, and of the current input symbol. You will receive as input the encoding of a function, and the input string.

As for the specific language at hand: the $\$$ in the middle actually makes it quite easy to design a transition function for this language. Without it, you would have a more difficult (and more interesting) problem. Just push symbols into one of the stacks and wait for the $\$$ to come up. You can then start using the other stack for the second half of the input string. Pop them both together. If in the process all symbols match, and in the end both stacks are empty, accept.

As you can see, we won't necessarily use the two stacks as if they stood for the content of the tape at each side of the head of a Turing machine.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41975