Pushdown automaton

In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data. In Computer science, a stack is an Abstract data type and Data structure based on the principle of Last In First Out (LIFO

1 Operation
2 Formal Definition
3 Example
4 Understanding the computation process
5 Generalized Pushdown Automaton (GPDA)
6 See also
7 External links
8 References

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). In the Theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA is a Finite state machine where for each If a deterministic finite state machine is used, then the result is a deterministic pushdown automaton (DPDA), a strictly weaker device. In the Theory of computation, a deterministic finite state machine (also known as deterministic finite state automaton (DFSA or deterministic finite 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 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. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine. A linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of a Non-deterministic 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. In Formal language theory, a context-free grammar ( CFG) is a grammar in which every production rule is of the form V &rarr

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 \times \Sigma_{\epsilon} \times \Gamma_{\epsilon} \longrightarrow \mathcal{P}(Q \times \Gamma_{\epsilon} )$ is the transition function, where $\mathcal{P}(S)$ denotes the power set of $S$ . In Mathematics, given a set S, the power set (or powerset) of S, written \mathcal{P}(S P ( S)
$\,q_{0}\in\, Q$ is the start state
$\ Z$ is the initial stack symbol
$F\subset Q$ is the set of accepting states
$\Gamma_{\epsilon} = \Gamma\cup\{\epsilon\}$
$\Sigma_{\epsilon} = \Sigma\cup\{\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}\,\in\Gamma^{*}$ such that

$s_{i} = a_{i+1}t_{i},\,s_{i+1} = b_{i+1}t_{i},\, t_{i}\in\Gamma^{*}$

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) t h$ 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) t h$ transitional move and $b i + 1$ is the symbol to be added to the stack during the $(i + 1) t h$ transitional move.

Both $a i + 1$ and $b i + 1$ can be $ε$ .

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

If $\,a_{i+1}\neq\epsilon$ 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}\neq\epsilon$ , 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$ $δ$ (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$ $δ$ (q_j, $ε$ , a_j+1) if q_j $\notin$ {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 $δ$ (q₀, $\epsilon,\,\epsilon)$ = {(q₁, $)} where $ is the special symbol.

Example

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

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

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

$Σ$ = {0, 1}

$Γ$ = {0, $}

F = {q₁, q₄}

$δ$ (q₁, $ε$ , $ε$ ) = {(q₂, $), (q₁, $ε$ )}

$δ$ (q₂, 0, $ε$ ) = {(q₂, 0)}

$δ$ (q₂, 1, 0) = {(q₃, $ε$ )}

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

$δ$ (q₃, $ε$ , $) = {(q₄, $ε$ )}

$δ$ (q, w, a) = $Φ$ 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

δ

(q₁,

ε

ε

) $\rightarrow$ (q₂, $) to represent (q₂, $) $\in$

δ

(q₁,

ε

ε

)

s₀ =

ε

, s₁ = $, t =

ε

, a =

ε

, b = $

set r₀ = q₂

(ii)

δ

(r₀, 0,

ε

) =

δ

(q₂, 0,

ε

) $\rightarrow$ (q₂, 0)

s₁ = $, a =

ε

, t = $, b = 0, s₂ = 0$

set r₁ = q₂

(iii)

δ

(r₁, 0,

ε

) =

δ

(q₂, 0,

ε

) $\rightarrow$ (q₂, 0)

s₂ = 0$, a =

ε

, t = 0$, b = 0, s₃ = 00$

set r₂ = q₂

(iv)

δ

(r₂, 1, 0) =

δ

(q₂, 1, 0) $\rightarrow$ (q₃,

ε

)

s₃ = 00$, a = 0, t = 0$, b =

ε

, s₄ = 0$

set r₃ = q₃

(v)

δ

(r₃, 1, 0) =

δ

(q₃, 1, 0) $\rightarrow$ (q₃,

ε

)

s₄ = 0$, a = 0, t = $, b =

ε

, s₅ = $

(vi)

δ

(q₃,

ε

, $) $\rightarrow$ (q₄,

ε

)

s₅ = $, a = $, t =

ε

, b =

ε

, s₆ =

ε

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)

δ

(r₃,

ε

, a) =

δ

(q₃,

ε

, a)

Since s₄ = 0$, either a =

ε

or a = 0

In either case,

δ

(q₃,

ε

, a) =

Φ

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

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

δ

(r₀,

ε

ε

) $\rightarrow$ (q₁,

ε

)

Since q₁ is an accept state,

ε

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 \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 $δ$ (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 $\geq$ 0, y₁y₂. . . y_n $\in\Gamma^{*}$ , n $\geq$ 0.

Construct the following transitions for the PDA:

δ'

(q₁, w, x₁) $\longrightarrow$ (p₁,

ε

)

δ'

(p₁,

ε

, x₂) $\longrightarrow$ (p₂,

ε

)

$\vdots$

δ'

(p_m-1,

ε

, x_m) $\longrightarrow$ (p_m,

ε

)

δ'

(p_m,

ε

ε

) $\longrightarrow$ (p_m+1, y_n)

δ'

(p_m+1,

ε

ε

) $\longrightarrow$ (p_m+2, y_n-1)

$\vdots$

δ'

(p_m+n-1,

ε

ε

) $\longrightarrow$ (q₂, y₁)

External links

non-deterministic pushdown automaton, on Planet Math. In Computer science, a stack machine is a Model of computation in which the computer's memory takes the form of one or more stacks The term also refers In Formal language theory, a context-free grammar ( CFG) is a grammar in which every production rule is of the form V &rarr
JFLAP, simulator for several types of automata including nondeterministic pushdown automata

References

Michael Sipser (1997). Michael Fredric Sipser is a Professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. 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
n/a	Tree-adjoining etc. A formal language is a set of words, ie finite strings of letters, or symbols. In Formal semantics, Computer science and Linguistics, a formal grammar (also called formation rules) is a precise description of a Formal Within the field of Computer science, specifically in the area of Formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger In Formal semantics, Computer science and Linguistics, a formal grammar (also called formation rules) is a precise description of a Formal A formal language is a set of words, ie finite strings of letters, or symbols. In Formal language theory an unrestricted grammar is a Formal grammar on which no restrictions are made on the left and right sides of the grammar's productions In Mathematics, Logic and Computer science, a recursively enumerable language is a type of Formal language which is also called partially Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm A recursive language in Mathematics, Logic and Computer science, is a type of Formal language which is also called recursive, A context-sensitive grammar (CSG is a Formal grammar in which the left-hand sides and right-hand sides of any Production rules may be surrounded by a context of In Theoretical computer science, a context-sensitive language is a Formal language that can be defined by a Context-sensitive grammar. A linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of a Non-deterministic Turing machine. An indexed grammar is a Formal grammar which describes Indexed languages They have three disjoint sets of symbols the usual terminals and nonterminals and the indices Indexed languages are a class of Formal languages discovered by Alfred Aho; they are described by Indexed grammars and can be recognized by Nested stack 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 Tree-adjoining grammar (TAG is a grammar formalism defined by Aravind Joshi.	(Mildly context-sensitive)	Embedded pushdown
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
n/a		Star-free	Counter-Free
Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it. In Formal grammar theory mildly context-sensitive languages are a class of Formal languages which can be efficiently parsed but still possess enough context An embedded pushdown automaton or EPDA is a Computational model that parse languages in the Tree-adjoining grammar (TAG In Formal language theory, a context-free grammar ( CFG) is a grammar in which every production rule is of the form V &rarr In Formal language theory, a context-free language is a language generated by some Context-free grammar. In Formal grammar theory the deterministic context-free grammars (DCFGs are a Proper subset of the Context-free grammars. A deterministic context-free language is a Formal language which is defined by a Deterministic context-free grammar. 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 Strictly regular grammars In Computer science, a right regular grammar (also called right linear grammar) is a Formal grammar ( N, A Regular language is said to be star-free if it can be described by a Regular expression constructed from the letters of the alphabet, the Empty set

Dictionary

-noun

(computing theory) A 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.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Operation

Formal Definition

Example

Understanding the computation process

Generalized Pushdown Automaton (GPDA)

See also

External links

References

Dictionary

pushdown automaton

-noun