# How exactly does a two stack pushdown automaton work?

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.

• Your question is unclear. Do you want to understand how the 2-PDA works, in particular for the problem you are given, or do you ask how it simulates a Turing Machine (TM). A 2-PDA in general will simply read input left to right from the input tape and act on two stacks instead of one. for each transition. Acceptance can be by accepting states, though variations are possible as usual. A PDA does not have to save input in a stack. It stores in the stack(s) whatever is needed: Stack(s) and input alphabets can be unrelated (as for standard PDA). Apr 30, 2015 at 10:22
• Duplicate? Or this? Anyway, just follow the definition; it's not too different from implementing PDAs.
– Raphael
Apr 30, 2015 at 12:23
• @babou I wanted to understand how a 2-PDA works so that I am able to create one because I couldn't really figure it out. Thanks for your comment, it really helped :) @ Raphael I think it is not a duplicate because the other question dealt with a PDA that can move its reading head in both directions. I was talking about a PDA with two stacks. Apr 30, 2015 at 13:53
• Do you still need help. If not, you can try to answer your own question, and describe the way the 2-PDA can accept this language. The idea takes 2 or 3 lines at most. Apr 30, 2015 at 14:55

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. • Okay I save all the digits from the left of the$\$$and save them to the first stack. When I reach the \$$, I save all the digits on the right to the second stack. Now how do I "pop them both together"? Furthermore, how would the syntax look like? With normal PDAs, I note it as something like this: q1, (input digit) → q1, (stack digit), (new stack digit) How do I tell it to store it in the second stack? May 3, 2015 at 16:37