3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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). $\endgroup$
    – babou
    Commented Apr 30, 2015 at 10:22
  • $\begingroup$ Duplicate? Or this? Anyway, just follow the definition; it's not too different from implementing PDAs. $\endgroup$
    – Raphael
    Commented Apr 30, 2015 at 12:23
  • $\begingroup$ @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. $\endgroup$
    – Tim Lâm
    Commented Apr 30, 2015 at 13:53
  • $\begingroup$ 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. $\endgroup$
    – babou
    Commented Apr 30, 2015 at 14:55

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Tim Lâm
    Commented May 3, 2015 at 16:37
  • $\begingroup$ "Together" in "pop them both together" does not mean simultaneously. It's just that the transition function must make sure that, in the popping out phase, the symbols that are popped from the two stacks (one after the other) are equal. As to your second question, the two stacks have different names. A transition will name the stack it is changing. $\endgroup$
    – André Souza Lemos
    Commented May 3, 2015 at 18:08
  • $\begingroup$ Could you elaborate more on the popping out phase? As far as I knew, the PDA reads the word and at the end of the word, it stops. If the stack is empty or it is in its final state, the word is accepted. Now how do you pop all of the digits in the stack out? Is this a process designed for the 2-PDA or do you just have another transition at the empty word and pop the stacks out then? And then just check if they're the same? $\endgroup$
    – Tim Lâm
    Commented May 4, 2015 at 21:26
  • $\begingroup$ The 2-PDA can transition without consuming symbols from the input. I suggest that you look for a good textbook on formal languages, one that covers this topic in a way that suits your style of learning. $\endgroup$
    – André Souza Lemos
    Commented May 4, 2015 at 21:49
  • $\begingroup$ I got it working almost. Now last step is the popping out phase. For a computer program, could I just check the content of the two stacks and if they are the same, accept the word? Or is there any formal criteria I need to regard? $\endgroup$
    – Tim Lâm
    Commented May 10, 2015 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.