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

Operation

a diagram of the pushdown automaton

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 at the input signal and the 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.

In general pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations while others are not. Thus we have a model which is technically known as a "nondeterministic pushdown automaton" (NPDA). Thus, nondeterminism means that there may be more than just one transition available to follow, given an input signal, state, and stack symbol. If in any situation only one transition is available as continuation of the computation, then the result is a deterministic pushdown automaton (DPDA), a strictly weaker device.

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.

Pushdown automata are equivalent to context-free grammars: 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, which is easy to prove. It is harder to show the converse: 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.

Formal Definition

A PDA is formally defined as a 7-tuple:

M=(Q,\ \Sigma,\ \Gamma,\ \delta, \ q_{0},\ Z, \ F) where

• \, Q is a finite set of states
• \,\Sigma is a finite set which is called the input alphabet
• \,\Gamma is a finite set which is called the stack alphabet
• \,\delta is a finite subset of Q \times (\Sigma \cup\{\varepsilon\}) \times \Gamma = Q \times \Gamma^* , the transition relation.
• \,q_{0}\in\, Q is the start state
• \ Z is the initial stack symbol
• F\subseteq Q is the set of accepting states

An element (p,a,A,q,\alpha) is a transition of M. It has the intended meaning that M, in state p, with a on the input and with A as topmost stack symbol, may read a, change the state to q, pop A, replacing it by \alpha. The letter \epsilon (epsilon) denotes the empty string and the '(\Sigma \cup\{\varepsilon\})' component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.

In many texts the transition relation is replaced by an (equivalent) transition function \delta mapping Q \times (\Sigma \cup\{\varepsilon\}) \times \Gamma into finite subsets of Q \times \Gamma^*. Here \delta(p,a,A) contains all possible actions in state p with A on the stack, while reading a on the input. One writes (q,\alpha) \in \delta(p,a,A) for the function precisely when (p,a,A,q,\alpha) \in\delta for the relation.

Computations

a step of the pushdown automaton

In general pushdown automata are nondeterministic meaning that in a given instantaneous description (p,w,\beta) there may be several possible steps. Any of these steps can be chosen in a computation. With the above definition in each step always a single symbol (top of the stack) is popped, replacing it with as many symbols as necessary. As a consequence no step is defined when the stack is empty.

Computations of the pushdown automaton are sequences of steps. The computation starts in the initial state q_{0} with the initial stack symbol Z on the stack, and a string w on the input tape, thus with initial description (q_{0},w,Z). There are two modes of accepting. The pushdown automaton either accepts by final state, which means after reading its input the automaton reaches an accepting state (in F), or it accepts by empty stack (\varepsilon), which means after reading its input the automaton empties its stack. The first acceptance mode uses the internal memory (state), the second the external memory (stack).

Formally one defines

1. L(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (f,\varepsilon,\gamma) with f \in F and \gamma \in \Gamma^* \} (final state)
2. N(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (q,\varepsilon,\varepsilon) with q \in Q \} (empty stack)

Here \vdash_M^* represents the reflexive and transitive closure of the step relation \vdash_M meaning any number of consecutive steps (zero, one or more).

For each single pushdown automaton these two languages need to have no relation: they may be equal but usually this is not the case. A specification of the automaton should also include the intended mode of acceptance. Taken over all pushdown automata both acceptance conditions define the same family of languages.

Theorem. For each pushdown automaton M one may construct a pushdown automaton M' such that L(M)=N(M'), and vice versa, for each pushdown automaton M one may construct a pushdown automaton M' such that N(M)=L(M')

Example

The following is the formal description of the PDA which recognizes the language \{0^n1^n \mid n \ge 0 \} by final state:

PDA for \{0^n1^n \mid n \ge 0\} (by final state)

Q = \{ p,q,r \}

\Sigma = \{0, 1\}

\Gamma = \{A, Z\}

F = \{r\}

\delta consists of the following six instructions:

(p,0,Z,p,AZ), (p,0,A,p,AA), (p,\epsilon,Z,q,Z), (p,\epsilon,A,q,A), (q,1,A,q,\epsilon), and (q,\epsilon,Z,r,Z).

In words, in state p for each symbol 0 read one A is pushed onto the stack. Pushing symbol A on top of another A is formalized as replacing top A by AA. In state q for each symbol 1 read one A is popped. At any moment the automaton may move from state p to state q, while it may move from state q to accepting state r only when the stack consists of a single Z.

There seems to be no generally used representation for PDA. Here we have depicted the instruction (p,a,A,q,\alpha) by an edge from state p to state q labelled by a; A/\alpha (read a; replace A by \alpha).

Understanding the computation process

accepting computation for 0011

(a) Input string = 0011. There are various computations, depending on the moment the move from state p to state q is made. Only one of these is accepting.

(i) (p,0011,Z) \vdash (q,0011,Z) \vdash (r,0011,Z). The final state is accepting, but the input is not accepted this way as it has not been read.

(ii) (p,0011,Z) \vdash (p,011,AZ) \vdash (q,011,AZ). No further steps possible.

(iii) (p,0011,Z) \vdash (p,011,AZ) \vdash (p,11,AAZ) \vdash (q,11,AAZ) \vdash (q,1,AZ) \vdash (q,\epsilon,Z) \vdash (r,\epsilon,Z). Accepting computation: ends in accepting state, while complete input has been read.

(b) Input string = 00111. Again there are various computations. None of these is accepting.

(i) (p,00111,Z) \vdash (q,00111,Z) \vdash (r,00111,Z). The final state is accepting, but the input is not accepted this way as it has not been read.

(ii) (p,00111,Z) \vdash (p,0111,AZ) \vdash (q,0111,AZ). No further steps possible.

(iii) (p,00111,Z) \vdash (p,0111,AZ) \vdash (p,111,AAZ) \vdash (q,111,AAZ) \vdash (q,11,AZ) \vdash (q,1,Z) \vdash (r,1,Z). The final state is accepting, but the input is not accepted this way as it has not been (completely) read.

Generalized Pushdown Automaton (GPDA)

A GPDA is a PDA which writes an entire string to the stack or removes an entire string from the stack in one step.

A GPDA is formally defined as a 6-tuple M=(Q,\ \Sigma,\ \Gamma,\ \delta, \ q_{0}, \ F)

where Q, \Sigma\,, \Gamma\,, q₀ and F are defined the same way as a PDA.

\,\delta: Q \times \Sigma_{\epsilon} \times \Gamma^{*} \longrightarrow P( Q \times \Gamma^{*} ) is the transition function.

Computation rules for a GPDA are the same as a PDA except that the a_i+1's and b_i+1's are now strings intead of symbols.

GPDA's and PDA's are equivalent in that if a language is recognized by a PDA, it is also recognized by a GPDA and vice versa.

One can formulate an analytic proof for the equivalence of GPDA's and PDA's using the following simulation:

Let \delta(q₁, w, x₁x₂...x_m) \longrightarrow (q₂, y₁y₂...y_n) be a transition of the GPDA

where q₁, q₂ \in Q, w \in\Sigma_{\epsilon}\,, x₁x₂...x_m \in\Gamma^{*}, m\geq0, y₁y₂...y_n \in\Gamma^{*}, n\geq0.

Construct the following transitions for the PDA:

\delta^{'}(q₁, w, x₁) \longrightarrow (p₁, \epsilon)

\delta^{'}(p₁, \epsilon, x₂) \longrightarrow (p₂, \epsilon)

\vdots

\delta^{'}(p_m-1, \epsilon, x_m) \longrightarrow (p_m, \epsilon)

\delta^{'}(p_m, \epsilon, \epsilon ) \longrightarrow (p_m+1, y_n)

\delta^{'}(p_m+1, \epsilon, \epsilon ) \longrightarrow (p_m+2, y_n-1)

\vdots

\delta^{'}(p_m+n-1, \epsilon, \epsilon ) \longrightarrow (q₂, y₁)

See also

• Stack machine
• Context-free grammar
• Finite automaton
• Nondeterministic finite state machine

External links

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

References

• Section 2.2: Pushdown Automata, pp.101–114.

ar:????????? ??? ??????? ?? ?????? bs:Potisni automat cs:Zásobníkový automat de:Kellerautomat es:Autómata con pila fr:Automate ŕ pile hr:Potisni automat it:Automa a pila he:?????? ?????? mk:Pushdown ??????? ja:?????????????? pl:Automat ze stosem ru:??????? ? ?????????? ??????? sk:Zásobníkový automat fi:Pinoautomaatti zh:?????