[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

Let the symbol "move to" indicate a move of the npda, and suppose that delta(q1, a, x) = {(q2, y), ...}. Then the following move is possible:
(q1, aW, xZ) move to (q2, 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 q1 to state q2, 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.

Copyright 1996 by David Matuszek
Last modified Mar 4, 1996