Pushdown automaton

From Wikipedia, the free encyclopedia

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

1 Operation
2 Definition
3 Example
4 See also
5 External links
6 References

[edit] Operation

Pushdown automata differ from normal finite state machines in two ways:

They can use the top of the stack to decide which transition to take.
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 have no 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. 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.

The (underlying) finite automaton is specifically a nondeterministic finite state machine, giving what is technically known as a "nondeterministic pushdown automaton" (NPDA). If a deterministic finite state machine is used, then the result is a deterministic pushdown automaton (DPDA), a strictly weaker device. Nondeterminism 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.

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. Conversely, 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.

[edit] Definition

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
$σ$ (or sometimes $δ$ ) is a finite transition relation $(Q \times ( \Sigma \cup \left \{ \epsilon \right \} ) \times \Phi) \longrightarrow P( Q \times \Phi ^{*} )$
$s$ is an element of $Q$ the start state
$Ω$ is the initial 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: 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 $Ω$ for the initial stack symbol, instead adding a first transition which writes a start symbol to the stack.

[edit] Example

The context-free language $\{a^kb^k | k \ge 0 \}$ can be recognized with the following pushdown automaton:

$M = ({q 0, q 1, q 2, q 3},{a, b},{A,$ $A$ $},δ, q 0,{q 0, q 3}),$

where the transitions are

$δ(q 0, a,ε) = {(q 1,$ $A$ $)}$

$δ(q 1, a,ε) = {(q 1, A)}$

$δ(q 1, b, A) = {(q 2,ε)}$

$δ(q 1, b,$ $A$ $) = {(q 3,ε)}$

$δ(q 2, b, A) = {(q 2,ε)}$

$δ(q 2, b,$ $A$ $) = {(q 3,ε)}$

$δ(q,θ,ρ) =$ Φ for any other $(q,θ,ρ)$

The meaning of the transitions can be explained by looking at the first transition

$δ(q 0, a,ε) = {(q 1,$ $A$ $)}$

When $q 0$ is the current state, $a$ is the input and $ε$ is taken from the top of the stack then the state changes to $q 1$ and $A$ is written to the top of the stack.

[edit] See also

[edit] External links

non-deterministic pushdown automaton, on Planet Math.
JFLAP, simulator for several types of automata including nondeterministic pushdown automata

[edit] References

Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 2.2: Pushdown Automata, pp.101–114.

Automata theory: formal languages and formal grammars
Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
Type-2	Context-free	Context-free	Nondeterministic Pushdown
n/a	Deterministic Context-free	Deterministic Context-free	Deterministic Pushdown
Type-3	Regular	Regular	Finite
Each category of languages or grammars is a proper subset of the category directly above it.