Pushdown Automaton

A Pushdown Automaton is an automaton that employs a stack ADT.

• AKA: PDA.
• Context:
  • It can range from being a Deterministic Pushdown Automata to being a Non-Deterministic Pushdown Automata.
• See: Nested Stack Automaton, Automata Theory, Finite-State Machine, Turing Machine, Deterministic Context-Free Language, Context-Free Language, Parser, Stack (Abstract Data Type).

---

---

References

2017

• (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/Pushdown_automaton Retrieved:2017-1-27.
  • In computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.

    Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines.

     Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design.

    The term "pushdown" refers to the fact that the stack can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than pushdown automata.

    A nested stack automaton allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.

---