associated with deterministic context-free languages.
7.1 Nondeterministic Pushdown Automata
A schematic representation of a pushdown automaton is given in Figure 7.1.
Each move of the control unit reads a symbol from the input file, while at the
same time changing the contents of the stack through the usual stack operations.
Each move of the control unit is determined by the current input symbol as well
as by the symbol currently on top of the stack. The result of the move is a new
state of the control unit and a change in the top of the stack.
Definition of a Pushdown Automaton
Formalizing this intuitive notion gives us a precise definition of a pushdown
automaton.
Figure 7.1
Definition 7.1
A nondeterministic pushdown accepter (npda) is defined by the septuple
where