# Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?

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.

• See here for the power of two-stack PDA, and here for techniques to show that the language is not context-free. – Raphael Apr 2 '13 at 7:15

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 :)

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

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).

• 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. – frafl Mar 29 '13 at 19:27
• No need for that, problem requires me to draw 2-Stack PDA for that – Iancovici Mar 29 '13 at 19:35
• Well, you should not hand in the proof, just make sure you understand that this can't be context free. – frafl Mar 29 '13 at 19:42