Encyclopedia > Pushdown automaton

  Article Content

Pushdown automaton

Pushdown automata are abstract devices defined in automata theory. They are similar to finite automata, except that they have access to a potentially unlimited amount of memory in the form of a single stack. Pushdown automata exist in deterministic and non-deterministic varieties, and the two are not equipotent. Every pushdown automaton accepts a formal language. The languages accepted by the non-deterministic pushdown automata are precisely the context-free languages.

If we allow a finite automaton access to two stacks instead of just one, we obtain a device much more powerful than a pushdown automaton: it is equivalent to a Turing machine.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Canadian Music Hall of Fame

... Denny Doherty[?] 1996 John Kay[?] 1996 Dominic Troiano[?] 1996 Zal Yanovsky 1997 Gil Evans[?] 1997 Lenny Breau[?] 1997 Maynard Ferguson 1997 Moe Koffman[?] ...

 
 
 
This page was created in 45.7 ms