Push Down Automata which has 2 stacks
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.
Related videos on Youtube
Comments
-
nurgasemetey over 3 years
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!
-
Tara B over 10 yearsWhat precisely do you mean by 'recognised by two PDA's'? And do you in fact mean by two PDA's, as in the body of the question, or by a PDA with two stacks, as in the title?
-
nurgasemetey over 10 yearsI mean language which cannot be recognized by PDA with one stack, but which can be recognized by PDA with two stacks
-
Tara B over 10 yearsWell, depending on how you define a PDA with two stacks, it can even be as powerful as a Turing machine!
-