4
$\begingroup$

Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar?

I don't believe this has a context-free grammar, but please correct me if I'm wrong.

Improve this question
$\endgroup$
1
  • $\begingroup$ See here for the power of two-stack PDA, and here for techniques to show that the language is not context-free. $\endgroup$
    – Raphael ♦
    Apr 2, 2013 at 7:15

2 Answers 2

Reset to default
6
$\begingroup$

A two-stack PDA is equivalent in computing power to a Turing machine. Since a Turing machine can accept that language (stated without proof), a two-stack PDA can as well. The actual definition of such a machine is left as an exercise :)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! P.S. What did you mean about stated without proof ? Are there languages which a turing machines can't accept? $\endgroup$
    – Iancovici
    Mar 29, 2013 at 13:25
  • 2
    $\begingroup$ @echadromani a valid program that never finishes under some input (look up the halting problem for more input) $\endgroup$
    – ratchet freak
    Mar 29, 2013 at 13:55
2
$\begingroup$

You don't even need to know about the equivalence to a Turing Machine to decide this language and if it was the intention of this exercise to come up with the equivalence, the language is (IMHO) to easy to motivate this.

A simple two-stack PDA for this language works like this:

  1. Put $n$ on both counters, while counting $a$s.
  2. Use counter one to check the $b$s.
  3. Count up on counter one and down on counter two to check the $c$s.
  4. Check the $d$s.

I left out some details, but filling them should be easy.

By the way: You should not believe that this language is not context free, but prove it (it should be obvious which word to choose as a counter example using the pumping lemma).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't think it's context free, I think it's easy to prove that it's not context free, therefore I ask you not to believe, but to prove. $\endgroup$
    – frafl
    Mar 29, 2013 at 19:27
  • $\begingroup$ No need for that, problem requires me to draw 2-Stack PDA for that $\endgroup$
    – Iancovici
    Mar 29, 2013 at 19:35
  • $\begingroup$ Well, you should not hand in the proof, just make sure you understand that this can't be context free. $\endgroup$
    – frafl
    Mar 29, 2013 at 19:42

Your Answer

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

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