Push Down Automata which has 2 stacks

1,911

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.

Share:
1,911

Related videos on Youtube

nurgasemetey
Author by

nurgasemetey

Just learner

Updated on May 11, 2020

Comments

  • nurgasemetey
    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
      Tara B over 10 years
      What 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
      nurgasemetey over 10 years
      I mean language which cannot be recognized by PDA with one stack, but which can be recognized by PDA with two stacks
    • Tara B
      Tara B over 10 years
      Well, depending on how you define a PDA with two stacks, it can even be as powerful as a Turing machine!