Pushdown automaton

related topics
{math, number, function}
{system, computer, user}

In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data.



Pushdown automata differ from finite state machines in two ways:

Pushdown automata choose a transition by indexing a table by input signal, current state, and the symbol at the top of the stack. This means that those three parameters completely determine the transition path that is chosen. Finite state machines just look at the input signal and the current state: they have no stack to work with. Pushdown automata add the stack as a parameter for choice.

Pushdown automata can also manipulate the stack, as part of performing a transition. Finite state machines choose a new state, the result of following the transition. The manipulation can be to push a particular symbol to the top of the stack, or to pop off the top of the stack. The automaton can alternatively ignore the stack, and leave it as it is. The choice of manipulation (or no manipulation) is determined by the transition table.

Put together: Given an input signal, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack.

In general pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations while others are not. Thus we have a model which is technically known as a "nondeterministic pushdown automaton" (NPDA). Nondeterminism means that there may be more than just one transition available to follow, given an input signal, state, and stack symbol. If in every situation only one transition is available as continuation of the computation, then the result is a deterministic pushdown automaton (DPDA), a strictly weaker device.

If we allow a finite automaton access to two stacks instead of just one, we obtain a more powerful device, equivalent in power to a Turing machine. A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine.

Pushdown automata are equivalent to context-free grammars: for every context-free grammar, there exists a pushdown automaton such that the language generated by the grammar is identical with the language generated by the automaton, which is easy to prove. The reverse is true, though harder to prove: for every pushdown automaton there exists a context-free grammar such that the language generated by the automaton is identical with the language generated by the grammar.

Formal Definition

A PDA is formally defined as a 7-tuple:

M=(Q,\  \Sigma,\  \Gamma,\  \delta, \ q_{0},\ Z, \ F) where

Full article ▸

related documents
Axiom schema of replacement
Heine–Borel theorem
Euclidean algorithm
Glossary of topology
Binary relation
Linear independence
Presentation of a group
Abstract interpretation
E (mathematical constant)
Type theory
Random variable
Algebraic structure
Linear combination
Probability density function
Ideal class group
IEEE 754-1985
Elliptic curve
Gaussian quadrature
Natural transformation
Fuzzy logic
Dijkstra's algorithm
Homology (mathematics)
Goldbach's conjecture
Absolute convergence
Euler characteristic
Galois theory
Partition (number theory)
Wiener process