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.

$\endgroup$
  • $\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 '13 at 7:15
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 :)

$\endgroup$
  • $\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 '13 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 '13 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).

$\endgroup$
  • $\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 '13 at 19:27
  • $\begingroup$ No need for that, problem requires me to draw 2-Stack PDA for that $\endgroup$ – Iancovici Mar 29 '13 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 '13 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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