In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data. In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. ... Fig. ... Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ...

Operation

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

1. They can use the top of the stack to decide which 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 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. In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. ... In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. ... In automata theory, a deterministic pushdown automaton is a deterministic finite state machine that can make use of a stack containing data. ...

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. An artistic representation of a Turing Machine . ... A linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of 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. In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a nonterminal symbol and w is a string consisting of terminals and/or non-terminals. ...

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
• 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.

Example

The context-free language can be recognized with the following pushdown automaton:

M = ({q₀,q₁,q₂,q₃},{a,b},{A,A},δ,q₀,{q₀,q₃}),

where the transitions are

δ(q₀,a,ε) = {(q₁,A)}

δ(q₁,a,ε) = {(q₁,A)}

δ(q₁,b,A) = {(q₂,ε)}

δ(q₁,b,A) = {(q₃,ε)}

δ(q₂,b,A) = {(q₂,ε)}

δ(q₂,b,A) = {(q₃,ε)}

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

Here uses a start stack symbol A which insteads of initial stack symbol.

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

δ(q₀,a,ε) = {(q₁,A)}

When q₀ is the current state, a is the input and the stack is empty then the state changes to q₁ and A is written to the top of the stack.

δ(q₁,b,A) = {(q₂,ε)}

When q₁ is the current state, b is the input and A is taken from the top of the stack then the state changes to q₂ and pop off the top of the stack.

Image File history File links Automateapile. ...

See also

• Stack machine
• context-free grammar
• finite automaton

In computer science, a stack machine is a model of computation in which the computers memory takes the form of a stack. ... In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a nonterminal symbol and w is a string consisting of terminals and/or non-terminals. ... In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ...

External links

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

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.