# Pushdown automaton

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

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

The (underlying) finite automation 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.

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, and 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=\left(Q, Sigma, Gamma, delta, q_\left\{0\right\}, Z, F\right)$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$: $Q imes Sigma_\left\{epsilon\right\} imes Gamma_\left\{epsilon\right\} longrightarrow mathcal\left\{P\right\}\left(Q imes Gamma_\left\{epsilon\right\} \right)$ is the transition function, where $mathcal\left\{P\right\}\left(S\right)$ denotes the power set of $S$.
*$,q_\left\{0\right\}in, Q$ is the start state
*$Z$ is the initial stack symbol
*$Fsubseteq Q$ is the set of accepting states
*$Gamma_\left\{epsilon\right\} = Gammacup\left\{epsilon\right\}$
*$Sigma_\left\{epsilon\right\} = Sigmacup\left\{epsilon\right\}$

"Computation Definition 1"

For any PDA, $M=\left(Q, Sigma, Gamma, delta, q_\left\{0\right\}, F\right)$, a computation path is an ordered

(n+1)-tuple, $\left(q_\left\{0\right\},, q_\left\{1\right\}, ...., ,q_\left\{n\right\}\right)$, where $q_\left\{i\right\}$$in$ Q, n$geq$ 0, which satisfies the following conditions:

(i) $\left(q_\left\{i+1\right\}, b_\left\{i+1\right\}\right) in delta \left(q_\left\{i\right\}, w_\left\{i+1\right\}, a_\left\{i+1\right\}\right)$ for i = 0, 1, 2,......, n-1, :where $w_\left\{i+1\right\}in Sigma_\left\{epsilon\right\}, a_\left\{i+1\right\}, b_\left\{i+1\right\}in Gamma_\left\{epsilon\right\}$

(ii) $exists, s_\left\{0\right\},, s_\left\{1\right\},,s_\left\{2\right\},,s_\left\{3\right\},,cdots,,s_\left\{n\right\},inGamma^\left\{*\right\}$ such that

:$s_\left\{i\right\} = a_\left\{i+1\right\}t_\left\{i\right\},,s_\left\{i+1\right\} = b_\left\{i+1\right\}t_\left\{i\right\},, t_\left\{i\right\}inGamma^\left\{*\right\}$

Intuitively, a PDA, at any point in the computation process, faces multiple possibilities of whether to read a symbol from the top of the stack and replace it with another symbol, or read a symbol from the top of the stack and remove it without replacement, or not read any symbol from the stack but only push another symbol to it, or to do nothing. All these are governed by the simutaneous equations $s_\left\{i\right\} = a_\left\{i+1\right\}t_\left\{i\right\}$ and $s_\left\{i+1\right\} = b_\left\{i+1\right\}t_\left\{i\right\}$. $s_\left\{i\right\}$ is called the stack content immediately before the $\left(i+1\right)^\left\{th\right\}$ transitional move and $a_\left\{i+1\right\}$ is the symbol to be removed from the top of the stack. $s_\left\{i+1\right\}$ is the stack content immediately after the $\left(i+1\right)^\left\{th\right\}$ transitional move and $b_\left\{i+1\right\}$ is the symbol to be added to the stack during the $\left(i+1\right)^\left\{th\right\}$ transitional move.

Both $a_\left\{i+1\right\}$ and $b_\left\{i+1\right\}$ can be $epsilon$.

If $,a_\left\{i+1\right\} eqepsilon$ and $,b_\left\{i+1\right\} eqepsilon$, the PDA reads a symbol from the stack and replace it with another one.

If $,a_\left\{i+1\right\} eqepsilon$ and $,b_\left\{i+1\right\} = epsilon$, the PDA reads a symbol from the stack and remove it without replacement.

If $,a_\left\{i+1\right\} = epsilon$ and $,b_\left\{i+1\right\} eqepsilon$, the PDA simply adds a symbol to the stack.

If $,a_\left\{i+1\right\} = epsilon$ and $,b_\left\{i+1\right\} = epsilon$, the PDA leaves the stack unchanged.

Note that when n=0, the computation path is just the singleton (q0).

"Computation Definition 2"

For any input w = w1w2...wm, wi $in,Sigma$, m$geq$0, M accepts w if $exists$ a computation path $\left(q_\left\{0\right\},, q_\left\{1\right\}, ...., ,q_\left\{n\right\}\right)$ and a finite sequence r0, r1, r2,...rm $in$ Q, m$leq$n, such that

(i) For each i = 0, 1, 2,...m, ri is on the computation path. That is,: $exists$ f(i) where i$leq$f(i)$leq$n such that ri = qf(i)

(ii) (qf(i)+1, bf(i)+1) $in$ $delta$(ri, wi+1, af(i)+1) for each i = 0, 1, 2,...m-1.:where af(i)+1 and bf(i)+1 are defined as in Computation Definition 1.

(iii) (qj+1, bj+1) $in$ $delta$(qj, $epsilon$, aj+1) if qj $otin$ {r0, r1,...rm}:where aj+1 and bj+1 are defined as in Computation Definition 1.

(iv) rm = qn and rm $in$ F

Note that the above definitions do not provide a mechanism to test for an empty stack. To do so, one would need to write a special symbol on the stack at the beginning of every computation so that the PDA would recognize that the stack is effectively empty whenever it detects the special symbol. Formally, this is done by introducing the transition $delta$(q0, $epsilon,,epsilon\right)$ = {(q1, \$)} where \$ is the special symbol.

Example

The following is the formal description of the PDA which recognizes the language nato $\left\{0^n1^n | n ge 0 \right\}$:

$M=\left(Q, Sigma, Gamma, delta, q_\left\{1\right\}, F\right)$

Q = {q1, q2, q3, q4}

$Sigma$ = {0, 1}

$Gamma$ = {0, \$}

F = {q1, q4}

$delta$(q1, $epsilon$, $epsilon$) = {(q2, \$), (q1, $epsilon$)}

$delta$(q2, 0, $epsilon$) = {(q2, 0)}

$delta$(q2, 1, 0) = {(q3, $epsilon$)}

$delta$(q3, 1, 0) = {(q3, $epsilon$)}

$delta$(q3, $epsilon$, \$) = {(q4, $epsilon$)}

$delta$(q, w, a) = $Phi$ for any other values of state, input and stack symbols.

Understanding the computation process

The following illustrates how the above PDA computes on different input strings.

(a) Input string = 0011: (i) write $delta$(q1, $epsilon$, $epsilon$) $ightarrow$ (q2, \$) to represent (q2, \$) $in$ $delta$(q1, $epsilon$, $epsilon$)

:: s0 = $epsilon$, s1 = \$, t = $epsilon$, a = $epsilon$, b = \$

:: set r0 = q2

: (ii) $delta$(r0, 0, $epsilon$) = $delta$(q2, 0, $epsilon$) $ightarrow$ (q2, 0)

:: s1 = \$, a = $epsilon$, t = \$, b = 0, s2 = 0\$

:: set r1 = q2

: (iii) $delta$(r1, 0, $epsilon$) = $delta$(q2, 0, $epsilon$) $ightarrow$ (q2, 0)

:: s2 = 0\$, a = $epsilon$, t = 0\$, b = 0, s3 = 00\$

:: set r2 = q2

: (iv) $delta$(r2, 1, 0) = $delta$(q2, 1, 0) $ightarrow$ (q3, $epsilon$)

:: s3 = 00\$, a = 0, t = 0\$, b = $epsilon$, s4 = 0\$

:: set r3 = q3

: (v) $delta$(r3, 1, 0) = $delta$(q3, 1, 0) $ightarrow$ (q3, $epsilon$)

:: s4 = 0\$, a = 0, t = \$, b = $epsilon$, s5 = \$

: (vi) $delta$(q3, $epsilon$, \$) $ightarrow$ (q4, $epsilon$)

:: s5 = \$, a = \$, t = $epsilon$, b = $epsilon$, s6 = $epsilon$

:: set r4 = q4

: Since q4 is an accept state, 0011 is accepted.

: In summary, computation path = (q1, q2, q2, q2, q3, q3, q4)

: and (r0, r1, r2, r3, r4) = (q2, q2, q2, q3, q4)

(b) Input string = 001

: Computation moves (i), (ii), (iii), (iv) would have to be the same as in case (a), otherwise, the PDA would have come to a dead end before reaching (v).

: (v) $delta$(r3, $epsilon$, a) = $delta$(q3, $epsilon$, a)

:: Since s4 = 0\$, either a = $epsilon$ or a = 0

:: In either case, $delta$(q3, $epsilon$, a) = $Phi$

:: Therefore, computation comes to an end at r3 = q3 which is not an accept state. Therefore, 001 is rejected.

(c) Input string = $epsilon$

: Set r0 = q1, r1 = q1

: $delta$(r0, $epsilon$, $epsilon$) $ightarrow$ (q1, $epsilon$)

: Since q1 is an accept state, $epsilon$ is accepted.

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=\left(Q, Sigma, Gamma, delta, q_\left\{0\right\}, F\right)$

: where Q, $Sigma,$, $Gamma,$, q0 and F are defined the same way as a PDA.

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

Computation rules for a GPDA are the same as a PDA except that the ai+1's and bi+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$(q1, w, x1x2...xm) $longrightarrow$ (q2, y1y2...yn) be a transition of the GPDA

where q1, q2 $in$ Q, w $inSigma_\left\{epsilon\right\},$, x1x2...xm $inGamma^\left\{*\right\}$, m$geq$0, y1y2...yn $inGamma^\left\{*\right\}$, n$geq$0.

Construct the following transitions for the PDA:

::$delta^\left\{\text{'}\right\}$(q1, w, x1) $longrightarrow$ (p1, $epsilon$)

::$delta^\left\{\text{'}\right\}$(p1, $epsilon$, x2) $longrightarrow$ (p2, $epsilon$)

::::$vdots$

::$delta^\left\{\text{'}\right\}$(pm-1, $epsilon$, xm) $longrightarrow$ (pm, $epsilon$)

::$delta^\left\{\text{'}\right\}$(pm, $epsilon$, $epsilon$ ) $longrightarrow$ (pm+1, yn)

::$delta^\left\{\text{'}\right\}$(pm+1, $epsilon$, $epsilon$ ) $longrightarrow$ (pm+2, yn-1)

::::$vdots$

::$delta^\left\{\text{'}\right\}$(pm+n-1, $epsilon$, $epsilon$ ) $longrightarrow$ (q2, y1)

ee also

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

* [http://planetmath.org/encyclopedia/PushdownAutomaton.html non-deterministic pushdown automaton,] on Planet Math.
* [http://www.jflap.org JFLAP] , simulator for several types of automata including nondeterministic pushdown automata

References

* Section 2.2: Pushdown Automata, pp.101&ndash;114.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• pushdown automaton — noun An automaton with finitely many states that also can use one unbounded stack of memory; the automaton may only push, pop, or read the top of the stack. Abbreviation: PDA …   Wiktionary

• Deterministic pushdown automaton — In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack. A deterministic… …   Wikipedia

• Embedded pushdown automaton — An embedded pushdown automaton or EPDA is a computational model that parse languages in the tree adjoining grammar (TAG). It is similar to the context free grammar parsing pushdown automaton, except that instead of using a stack (data structure)… …   Wikipedia

• Counter automaton — In computer science, a counter automaton is a Pushdown automaton with only two symbols, A and the initial symbol in (the finite set of stack symbols). This class of automata can recognize a subset of Context free languages, for instance the… …   Wikipedia

• Nested stack automaton — In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.[1] A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack… …   Wikipedia

• Deterministic automaton — is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence. A common deterministic automaton is a deterministic finite state machine (sometimes… …   Wikipedia

• Nested word — In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of… …   Wikipedia

• Chomsky hierarchy — Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of… …   Wikipedia

• Computation history — In computer science, a computation history is a sequence of steps taken by an abstract machine in the process of computing its result. Computation histories are frequently used in proofs about the capabilities of certain machines, and… …   Wikipedia

• Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia