Pushdown automaton
|
|
In particular automata theory, pushdown automata (PDA) are abstract devices that recognize context-free languages.
Informally, a pushdown automaton is a finite automaton that can make use of a stack.
Pushdown automatons differ from normal finite state machines in two ways: (1) They can use the top of the stack to figure out what transition to take. (2) They can manipulate the stack as part of performing a transition.
Pushdown automata choose a transition by indexing a table by input signal, current state, and the top of the stack. Normal finite state machines just look by input signal and current state- they don't have a stack to work with. Pushdown automata add the stack as a parameter for choice. Given an input signal, current state, and a given symbol at the top of the stack, a transition path is chosen.
Pushdown automata can also manipulate the stack, as part of performing a transition. Normal finite state machines choose a new state, the result of following the transition. But pushdown automata can also manipulate the stack. The manipulation can be to push a particular symbol to the top of the stack, the manipulation can be to pop off the top of the stack. Or, the automata can ignore the stack, and leave it as it is. The choice of manipulation (or no manipulation) is determined by the transition table.
Put together: A given input signal, current state, and stack symbol, can follow a transition to another state, and an optional stack manipulation.
The finite automaton is usually a nondeterministic finite state machine, which is called a "nondeterministic pushdown automaton", or "NPDA," since deterministic pushdown automata cannot recognize all context-free languages. This means that there may be more than just one transition available to follow, given an input signal, state, and stack symbol.
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:
<math>W=(Q,\Sigma,\Phi,\sigma,s,\Omega,F)<math> where
- <math>Q<math> is a finite set of states
- <math>\Sigma<math> is a finite set of the input alphabet
- <math>\Phi<math> is a finite set of the stack alphabet
- <math>\sigma<math> is a finite transition relation <math>(Q \times ( \Sigma \cup \left \{ \epsilon \right \} ) \times \Phi) \longrightarrow P( Q \times \Phi ^{*} )<math>
- <math>s<math> is an element of <math>Q<math> the start state
- <math>\Omega<math> is the initial stack symbol
- <math>F<math> is subset of <math>Q<math>, 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: a final state can perform a pop loop to get to an empty stack, and a machine can detect an empty stack and enter a final state by detecting a unique symbol pushed by the initial state.
Some use a 6-tuple, dropping the <math>\Omega<math> for the initial stack symbol, instead adding a first transition which writes a start symbol to the stack.
See also
- Stack machine
- non-deterministic pushdown automaton, (http://planetmath.org/encyclopedia/PushdownAutomaton.html) on Planet Math.
- Context Free Automata and Pushdown Automata, (http://www.cs.bham.ac.uk/~axj/teaching/2003-4/models/handouts/handout3.pdf) from the University of Birminghamcs:Zásobníkový automat