Push Down Automata which has 2 stacks

Question

I am doing homework in Formal Languages. I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA. Thanks!

Answer 1

The standard example is to build a recognizer for the language $$ L=\{0^n1^n2^n\ |\ n > 0\} $$ You probably already know that this is not a context-free language, so cannot be recognized by a one-stack PDA (if you don't know this fact, it's easy to come up with a pumping lemma proof that it isn't a CFL).

However, it's easy to build a two-stack recognizer for this. Informally we do this:

• As long as the input symbol is 0, push a marker on both stacks
• As long as the input symbol is 1, pop the first stack
• As long as the input symbol is 2, pop the second stack

Of course, there are some things you'll have to add to this program, like how to recognize that you've read the right number of 1s and 2s and what to do if the input isn't of the form you need. It should be easy enough for you to fill in the details.