|
In computer science, in particular automata theory, pushdown automata (PDA) are abstract
devices that recognize context-free languages.
Informally, a pushdown automaton is a finite automaton
outfitted with access to a potentially unlimited amount of memory in the form of a single stack. The finite automaton in question is usually nondeterministic (resulting in a nondeterministic pushdown automaton or NPDA) since deterministic pushdown automata
cannot recognize all context-free languages.
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.
A NPDA W can be defined as a 7-tuple:
W = (Q,Σ,Φ,σ,s,Ω,F) 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.
There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two
are easily shown to be equivalent.
See also
|