[Overview] [Previous] [Next]

NPDA Execution

Suppose someone is in the middle of stepping through a string with a dfa, and we need to take over and finish the job. We will need to know two things: (1) the state the dfa is in, and (2) what the remaining input is. But if the automaton is an npda instead of a dfa, we also need to know (3) the contents of the stack.

An instantaneous description of a pushdown automaton is a triplet (q, w, u), where

q is the current state of the automaton,
w is the unread part of the input string, and
u is the stack contents (written as a string, with the leftmost symbol at the top of the stack).

Let the symbol "

" indicate a move of the npda, and suppose that

(q₁, a, x) = {(q₂, y), ...}. Then the following move is possible: (q₁, aW, xZ)

(q₂, W, yZ) where W indicates the rest of the string following the a, and Z indicates the rest of the stack contents underneath the x. This notation says that in moving from state q₁ to state q₂, an a is consumed from the input string aW, and the x at the top (left) of the stack xZ is replaced with y, leaving yZ on the stack.