Information About

Pushdown Automaton
  CATEGORIES ABOUT PUSHDOWN AUTOMATON
   
automata
   
computational models
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




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

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 6-tuple:

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

  • \, Q is a finite set of states

  • \,\Sigma is a finite set of the input alphabet

  • \,\Gamma is a finite set of the stack alphabet

  • \,\delta: Q imes \Sigma_{\epsilon} imes \Gamma_{\epsilon} \longrightarrow P( Q imes \Gamma_{\epsilon} ) is the transition function

  • q_{0} is the start state

  • F\subset Q is the set of accept 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}

  • } such that


  • }


Intuitively, a PDA, at any point in the computation process, faces a 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 does 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}
eq\epsilon and b_{i+1}
eq\epsilon, the PDA reads a symbol from the stack and replace it with another one.

If a_{i+1}
eq\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}
eq\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 (q0).

''Computation Definition 2''

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

(i) For each i = 0, 1, 2,...m, ri is on the computation path. That is,
: \exists f(i) where i\leqf(i)\leqn 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) = {(q1, $)} where $ is the special symbol.


EXAMPLE