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

"Computation Definition 1"

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

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

(i) $(q\_\{i+1\},\; b\_\{i+1\})\; in\; delta\; (q\_\{i\},\; w\_\{i+1\},\; a\_\{i+1\})$ for i = 0, 1, 2,......, n-1, :where $w\_\{i+1\}in\; Sigma\_\{epsilon\},\; a\_\{i+1\},\; b\_\{i+1\}in\; Gamma\_\{epsilon\}$

(ii) $exists,\; s\_\{0\},,\; s\_\{1\},,s\_\{2\},,s\_\{3\},,cdots,,s\_\{n\},inGamma^\{*\}$ such that

:$s\_\{i\}\; =\; a\_\{i+1\}t\_\{i\},,s\_\{i+1\}\; =\; b\_\{i+1\}t\_\{i\},,\; t\_\{i\}inGamma^\{*\}$

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\_\{i\}\; =\; a\_\{i+1\}t\_\{i\}$ and $s\_\{i+1\}\; =\; b\_\{i+1\}t\_\{i\}$. $s\_\{i\}$ is called the stack content immediately before the $(i+1)^\{th\}$ transitional move and $a\_\{i+1\}$ is the symbol to be removed from the top of the stack. $s\_\{i+1\}$ is the stack content immediately after the $(i+1)^\{th\}$ transitional move and $b\_\{i+1\}$ is the symbol to be added to the stack during the $(i+1)^\{th\}$ transitional move.

Both $a\_\{i+1\}$ and $b\_\{i+1\}$ can be $epsilon$.

If $,a\_\{i+1\}\; eqepsilon$ and $,b\_\{i+1\}\; eqepsilon$, the PDA reads a symbol from the stack and replace it with another one.

If $,a\_\{i+1\}\; eqepsilon$ and $,b\_\{i+1\}\; =\; epsilon$, the PDA reads a symbol from the stack and remove it without replacement.

If $,a\_\{i+1\}\; =\; epsilon$ and $,b\_\{i+1\}\; eqepsilon$, the PDA simply adds a symbol to the stack.

If $,a\_\{i+1\}\; =\; epsilon$ and $,b\_\{i+1\}\; =\; epsilon$, the PDA leaves the stack unchanged.

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

"Computation Definition 2"

For any input w = w₁w₂...w_m, w_i $in,Sigma$, m$geq$0, M accepts w if $exists$ a computation path $(q\_\{0\},,\; q\_\{1\},\; ....,\; ,q\_\{n\})$ and a finite sequence r₀, r₁, r₂,...r_m $in$ Q, m$leq$n, such that

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

(ii) (q_f(i)+1, b_f(i)+1) $in$ $delta$(r_i, w_i+1, a_f(i)+1) for each i = 0, 1, 2,...m-1.:where a_f(i)+1 and b_f(i)+1 are defined as in Computation Definition 1.

(iii) (q_j+1, b_j+1) $in$ $delta$(q_j, $epsilon$, a_j+1) if q_j $otin$ {r₀, r₁,...r_m}:where a_j+1 and b_j+1 are defined as in Computation Definition 1.

(iv) r_m = q_n and r_m $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$(q₀, $epsilon,,epsilon)$ = {(q₁, $)} where $ is the special symbol.

Example

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

$M=(Q,\; Sigma,\; Gamma,\; delta,\; q\_\{1\},\; F)$

Q = {q₁, q₂, q₃, q₄}

$Sigma$ = {0, 1}

$Gamma$ = {0, $}

F = {q₁, q₄}

$delta$(q₁, $epsilon$, $epsilon$) = {(q₂, $), (q₁, $epsilon$)}

$delta$(q₂, 0, $epsilon$) = {(q₂, 0)}

$delta$(q₂, 1, 0) = {(q₃, $epsilon$)}

$delta$(q₃, 1, 0) = {(q₃, $epsilon$)}

$delta$(q₃, $epsilon$, $) = {(q₄, $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$(q₁, $epsilon$, $epsilon$) $ightarrow$ (q₂, $) to represent (q₂, $) $in$ $delta$(q₁, $epsilon$, $epsilon$)

:: s₀ = $epsilon$, s₁ = $, t = $epsilon$, a = $epsilon$, b = $

:: set r₀ = q₂

: (ii) $delta$(r₀, 0, $epsilon$) = $delta$(q₂, 0, $epsilon$) $ightarrow$ (q₂, 0)

:: s₁ = $, a = $epsilon$, t = $, b = 0, s₂ = 0$

:: set r₁ = q₂

: (iii) $delta$(r₁, 0, $epsilon$) = $delta$(q₂, 0, $epsilon$) $ightarrow$ (q₂, 0)

:: s₂ = 0$, a = $epsilon$, t = 0$, b = 0, s₃ = 00$

:: set r₂ = q₂

: (iv) $delta$(r₂, 1, 0) = $delta$(q₂, 1, 0) $ightarrow$ (q₃, $epsilon$)

:: s₃ = 00$, a = 0, t = 0$, b = $epsilon$, s₄ = 0$

:: set r₃ = q₃

: (v) $delta$(r₃, 1, 0) = $delta$(q₃, 1, 0) $ightarrow$ (q₃, $epsilon$)

:: s₄ = 0$, a = 0, t = $, b = $epsilon$, s₅ = $

: (vi) $delta$(q₃, $epsilon$, $) $ightarrow$ (q₄, $epsilon$)

:: s₅ = $, a = $, t = $epsilon$, b = $epsilon$, s₆ = $epsilon$

:: set r₄ = q₄

: Since q₄ is an accept state, 0011 is accepted.

: In summary, computation path = (q₁, q₂, q₂, q₂, q₃, q₃, q₄)

: and (r₀, r₁, r₂, r₃, r₄) = (q₂, q₂, q₂, q₃, q₄)

(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$(r₃, $epsilon$, a) = $delta$(q₃, $epsilon$, a)

:: Since s₄ = 0$, either a = $epsilon$ or a = 0

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

:: Therefore, computation comes to an end at r₃ = q₃ which is not an accept state. Therefore, 001 is rejected.

(c) Input string = $epsilon$

: Set r₀ = q₁, r₁ = q₁

: $delta$(r₀, $epsilon$, $epsilon$) $ightarrow$ (q₁, $epsilon$)

: Since q₁ 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=(Q,\; Sigma,\; Gamma,\; delta,\; q\_\{0\},\; F)$

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

:$,delta$: $Q\; imes\; Sigma\_\{epsilon\}\; imes\; Gamma^\{*\}\; longrightarrow\; P(\; Q\; imes\; 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 $inSigma\_\{epsilon\},$, x₁x₂...x_m $inGamma^\{*\}$, m$geq$0, y₁y₂...y_n $inGamma^\{*\}$, n$geq$0.

Construct the following transitions for the PDA:

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

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

::::$vdots$

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

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

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

::::$vdots$

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

ee also

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

External links

* [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–114.