<p>First: Student's heuristics. At your level, what <em>can</em> you prove? Equivalence with TM or PDA should work by simulation. Equivalence to LBA might be slightly harder. Anything in between is certainly harder. So start with the easy inclusions.</p>

<p>You can see very quickly that languages like $a^nb^nc^n$ that are not context-free can be accepted by a 2-PDA. So you are certainly stronger than PDA.</p>

<p>Next in line is TM. Of course, every 2-PDA can be simulated by a 2-TM which can in turn be simulated by a TM. Turns out that the other direction works out, too. Take a TM and simulate it by a 2-PDA. You can keep the state graph but have to translate reading/writing/moving to reading$^2$/writing$^2$. What can simulate the TM's head? Also, take care what happens if the TM accesses new fields.</p>

<p>Can you figure it out now?</p>

CC BY-SA 2.5
2010-10-25T07:05:15.340Z
Yes, thanks, that helps a lot.  I was sort of thinking along those lines myself, but seeing it written down helps to clarify things - I should be able to do it now.
a_m0d
CC BY-SA 2.5
2010-10-25T07:00:42.540Z
2010-10-25T07:00:42.540Z
Raphael
<p>In our CS class, we have a question about the computational power of PDA's (Push Down Automaton).  A 0-PDA (PDA with no stacks) is equivalent to an NFA (Non-deteministic Finite Automaton), while a 1-PDA (the standard PDA) is equivalent to a CFG (Context Free Grammar).</p>

<p>However, a 2-PDA (PDA with 2 stacks) is more powerful (recognises more languages) than a 1-PDA, because it is not limited to pushing and popping on 1 stack only, but can also use the second stack.</p>

<p>The problem that I have is that I don't know how to <em>prove</em> the greater power of the 2-PDA.  My first thought was that a 2-PDA would be equivalent to a Turing Machine, but then I realised that it still wouldn't <em>quite</em> provide arbitrary access to the stack.</p>

<p>How would I go about proving that a 2-PDA is more powerful than a 1-PDA?</p>

<p>(Could someone with enough rep please tag this as <kbd>homework</kbd><kbd>pda</kbd> - thanks)</p>

CC BY-SA 2.5
2010-10-25T06:25:09.977Z
Note that a turing machine does not have _arbitrary_ (random)access to its tape. It still needs to traverse it to find the place to modify. In any case, this site is not used for answering homework questions.
Dave Clarke
CC BY-SA 2.5
2010-10-25T06:46:09.967Z
@Dave - Sorry, I did not *really* mean *random*, but more the fact that it can access elements on either side of the current head position, rather than just the element at the top of the stack.  Also, I don't really want an answer for the question, just a push in the right direction - what sort of method could I use for solving this?
a_m0d
CC BY-SA 2.5
2010-10-25T06:48:10.993Z
a_m0d, homework questions are not on-topic for this site. Please read: http://meta.cstheory.stackexchange.com/questions/209/homework-or-things-that-look-like-homework
Ryan Williams
CC BY-SA 2.5
2010-10-25T06:52:17.740Z
@Ryan - So, I won't get *any* help on here then?  If not, please close this question and delete it, as I don't want it littering search results on this topic.
a_m0d
CC BY-SA 2.5
2010-10-25T06:55:50.937Z
Hint: you have two unbounded stacks. Each has two operations push and pop. Enough ingredients to do some powerful stuffs.
Dave Clarke
CC BY-SA 2.5
2010-10-25T07:01:17.220Z
Would CW be an alternative for homework problems?
Raphael
CC BY-SA 2.5
2010-10-25T07:05:41.550Z
@Raphael: I don't think so. It's a standard question that students should spent time thinking about, rather than being told the answer.
Dave Clarke
CC BY-SA 2.5
2010-10-25T07:13:15.200Z
@Raphael: No, and if there is any need for a hint the course instructor should decide about it, not you. By answering homework questions/providing hints **you are encouraging academic dishonesty**, **may cause the student get into serious trouble**, and **you are not really helping the student in learning stuff**. @a_m0d: Getting help in solving assignments and presenting work which is not yours has heavy punishments in most universities, I strongly advise you against it. If you want a hint, you should ask your instructor.
Kaveh
CC BY-SA 2.5
2010-10-25T07:16:55.063Z
@Kaveh - Our instructor has no problem with us asking for outside help *on this particular assignment* (he actually encourages it), and I am unable to contact him at the moment, which is why I decided to post here instead.  Also, I don't want to use someone else's work; all I asked for was a hint / push in the right direction
a_m0d
CC BY-SA 2.5
2010-10-25T07:21:53.933Z
Kaveh, I do not know where you studied but at my university the academic approach -- collaborating, talking to others -- is highly encouraged. Getting help is not considered dishonest. Of course it does not help anyone to be told the answer and not think about it, but this is not my/our responsibility. In my experience, being put on the right path often helps. This is why I outlined a general strategy in my answer and gave only a broad hint as well as noted specific problems with the simulation that is to be done.
Raphael
CC BY-SA 2.5
2010-10-25T07:24:17.347Z
Or, in other words: As long as an answer only describes how to think about the problem in a helpful way (maybe using a related example) and does _not_ solve the assignment in detail, I cannot see any harm.
Raphael
CC BY-SA 2.5
2010-10-25T07:30:22.173Z
@Raphael: I don't know where you have studied, but in places that I have studied and have taught, in most courses, students are not permitted to get help in solving assignments. In any case, the decision about getting help should be made by the course instructor, you are in no position to make that decision, and it does not have anything to do with your experience. Fortunately, I have checked the policy on this in some top CS departments a few months ago, and in all of those that I have checked presenting work which is not yours is academic dishonesty. I can give you some pointers if you want.
Kaveh
CC BY-SA 2.5
2010-10-25T07:35:24.820Z
@Raphael: Often with these sorts of questions, giving the right hint essentially gives the answer away, even if it does not solve the assignment. (Which is why my hint was deliberately vague.)
Dave Clarke
CC BY-SA 2.5
2010-10-25T07:39:30.653Z
@Dave - when I first read your comment, I didn't think that you told me anything new, but re-reading it, something just clicked; I was thinking of the solution in the wrong way, so that even though I kind of knew what direction to head in, it would have been very hard to write down a proof.  Thank you for still taking the time to give me a hint, even if you don't agree with homework questions on here.
a_m0d
CC BY-SA 2.5
2010-10-25T07:48:27.507Z
Anyway, this wasn't a research level question.
Kaveh
CC BY-SA 2.5
2010-10-25T11:07:21.903Z
@Kaveh: I am doing my Masters at TU Kaiserslautern, Germany. We usually work on assignments in groups. In some courses, literature research is even (implicitly) required. Since these assignments only serve the purpose of excercise and are not exams on their own, usual rules regarding plagiarism do not apply. In any case, the responsibility for not breaking rules lies with the asking person. Since we cannot know wether or not he does break any, closing because he might is a bad line of argumentation. Correct scope is another point entirely.
Raphael
CC BY-SA 2.5
2010-10-25T11:08:35.660Z
@Dave: Yes, you have to be very careful. But then, sometimes you have to see a similar proof first in order to be able to see the correct way.
Raphael
<tag-removed>
Computational power of a 2-PDA
a_m0d
# Computational power of a 2-PDA

(Asked by: username_0 on 2010-10-25)

In our CS class, we have a question about the computational power of PDA's (Push Down Automaton). A 0-PDA (PDA with no stacks) is equivalent to an NFA (Non-deteministic Finite Automaton), while a 1-PDA (the standard PDA) is equivalent to a CFG (Context Free Grammar).

However, a 2-PDA (PDA with 2 stacks) is more powerful (recognises more languages) than a 1-PDA, because it is not limited to pushing and popping on 1 stack only, but can also use the second stack.

The problem that I have is that I don't know how to *prove* the greater power of the 2-PDA. My first thought was that a 2-PDA would be equivalent to a Turing Machine, but then I realised that it still wouldn't *quite* provide arbitrary access to the stack.

How would I go about proving that a 2-PDA is more powerful than a 1-PDA?

(Could someone with enough rep please tag this as `homework``pda` - thanks)

**Tags:** tag-removed
> **Comments:**
> **username_1**: Note that a turing machine does not have _arbitrary_ (random)access to its tape. It still needs to traverse it to find the place to modify. In any case, this site is not used for answering homework questions.  
> **username_0**: @Dave - Sorry, I did not *really* mean *random*, but more the fact that it can access elements on either side of the current head position, rather than just the element at the top of the stack.  Also, I don't really want an answer for the question, just a push in the right direction - what sort of method could I use for solving this?  
> **username_2**: a_m0d, homework questions are not on-topic for this site. Please read: http://meta.cstheory.stackexchange.com/questions/209/homework-or-things-that-look-like-homework  
> **username_0**: @Ryan - So, I won't get *any* help on here then?  If not, please close this question and delete it, as I don't want it littering search results on this topic.  
> **username_1**: Hint: you have two unbounded stacks. Each has two operations push and pop. Enough ingredients to do some powerful stuffs.  
> **username_3**: Would CW be an alternative for homework problems?  
> **username_1**: @Raphael: I don't think so. It's a standard question that students should spent time thinking about, rather than being told the answer.  
> **username_4**: @Raphael: No, and if there is any need for a hint the course instructor should decide about it, not you. By answering homework questions/providing hints **you are encouraging academic dishonesty**, **may cause the student get into serious trouble**, and **you are not really helping the student in learning stuff**. @a_m0d: Getting help in solving assignments and presenting work which is not yours has heavy punishments in most universities, I strongly advise you against it. If you want a hint, you should ask your instructor.  
> **username_0**: @Kaveh - Our instructor has no problem with us asking for outside help *on this particular assignment* (he actually encourages it), and I am unable to contact him at the moment, which is why I decided to post here instead.  Also, I don't want to use someone else's work; all I asked for was a hint / push in the right direction  
> **username_3**: Kaveh, I do not know where you studied but at my university the academic approach -- collaborating, talking to others -- is highly encouraged. Getting help is not considered dishonest. Of course it does not help anyone to be told the answer and not think about it, but this is not my/our responsibility. In my experience, being put on the right path often helps. This is why I outlined a general strategy in my answer and gave only a broad hint as well as noted specific problems with the simulation that is to be done.  
> **username_3**: Or, in other words: As long as an answer only describes how to think about the problem in a helpful way (maybe using a related example) and does _not_ solve the assignment in detail, I cannot see any harm.  
> **username_4**: @Raphael: I don't know where you have studied, but in places that I have studied and have taught, in most courses, students are not permitted to get help in solving assignments. In any case, the decision about getting help should be made by the course instructor, you are in no position to make that decision, and it does not have anything to do with your experience. Fortunately, I have checked the policy on this in some top CS departments a few months ago, and in all of those that I have checked presenting work which is not yours is academic dishonesty. I can give you some pointers if you want.  
> **username_1**: @Raphael: Often with these sorts of questions, giving the right hint essentially gives the answer away, even if it does not solve the assignment. (Which is why my hint was deliberately vague.)  
> **username_0**: @Dave - when I first read your comment, I didn't think that you told me anything new, but re-reading it, something just clicked; I was thinking of the solution in the wrong way, so that even though I kind of knew what direction to head in, it would have been very hard to write down a proof.  Thank you for still taking the time to give me a hint, even if you don't agree with homework questions on here.  
> **username_4**: Anyway, this wasn't a research level question.  
> **username_3**: @Kaveh: I am doing my Masters at TU Kaiserslautern, Germany. We usually work on assignments in groups. In some courses, literature research is even (implicitly) required. Since these assignments only serve the purpose of excercise and are not exams on their own, usual rules regarding plagiarism do not apply. In any case, the responsibility for not breaking rules lies with the asking person. Since we cannot know wether or not he does break any, closing because he might is a bad line of argumentation. Correct scope is another point entirely.  
> **username_3**: @Dave: Yes, you have to be very careful. But then, sometimes you have to see a similar proof first in order to be able to see the correct way.  

---

## 1 answers

### Answer by username_3 on 2010-10-25. Score: 3 | Accepted answer

First: Student's heuristics. At your level, what *can* you prove? Equivalence with TM or PDA should work by simulation. Equivalence to LBA might be slightly harder. Anything in between is certainly harder. So start with the easy inclusions.

You can see very quickly that languages like $a^nb^nc^n$ that are not context-free can be accepted by a 2-PDA. So you are certainly stronger than PDA.

Next in line is TM. Of course, every 2-PDA can be simulated by a 2-TM which can in turn be simulated by a TM. Turns out that the other direction works out, too. Take a TM and simulate it by a 2-PDA. You can keep the state graph but have to translate reading/writing/moving to reading$^2$/writing$^2$. What can simulate the TM's head? Also, take care what happens if the TM accesses new fields.

Can you figure it out now?

> **Comments:**
> **username_0**: Yes, thanks, that helps a lot.  I was sort of thinking along those lines myself, but seeing it written down helps to clarify things - I should be able to do it now.  

---

