A *nondeterministic pushdown automaton (npda)* is basically
an nfa with a stack added to it.

We start with the formal definition of an nfa, which is a 5-tuple, and add two things to it:

- is a finite set of
symbols called the
*stack alphabet*, and - z
is the
*stack start symbol*.

A *nondeterministic pushdown automaton* or *npda*
is a 7-tuple

- Q is a finite set of
*states,* - is a the
*input alphabet,* - is the
*stack alphabet,* - is a
*transition function,* - q
_{0}Q is the*initial state,* - z
is the
*stack start symbol,*and - F Q is
a set of
*final states.*

Copyright © 1996 by David Matuszek

Last modified Mar 3, 1996