Pushdown automaton
In computer science, pushdown automata (PDA) are abstract devices defined in automata theory that recognize context-free languages.
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. Non-deterministic pushdown automata (NPDA) are more potent than deterministic pushdown automata: there exist languages that are recognized by some non-deterministic pushdown automaton but that cannot be recognized by any deterministic pushdown automaton.
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 - we obtain the equivalent to a Turing machine.
A NPDA W can be defined as a 7-tuple function:
where
- Q is a finite set of states
- Σ is a finite set of the input alphabet
- Φ is a finite set of the stack alphabet
- σ is a finite transition relation (Q × ( Σ & {ε}) × Φ) × ( Q × Φ* )
- s is an element of Q; the start state
- Ω is the inital stack symbol
- F is subset of Q, consisting of the final states.
Referenced By
Automaton | List of computability and complexity topics | List of computing topics | List of mathematical topics (P-R)
|
