1
$\begingroup$

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 homeworkpda - thanks)

$\endgroup$
17
  • 4
    $\begingroup$ 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. $\endgroup$ – Dave Clarke Oct 25 '10 at 6:25
  • 1
    $\begingroup$ a_m0d, homework questions are not on-topic for this site. Please read: meta.cstheory.stackexchange.com/questions/209/… $\endgroup$ – Ryan Williams Oct 25 '10 at 6:48
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Oct 25 '10 at 7:21
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Oct 25 '10 at 7:24
  • 3
    $\begingroup$ @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. $\endgroup$ – Raphael Oct 25 '10 at 11:07
3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – a_m0d Oct 25 '10 at 7:05

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