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.
|
![[Home]](wikipedia.png)