where q is the state of the control unit, w is the unread part of the input string,
and u is the stack contents (with the leftmost symbol indicating the top of the
stack), is called an instantaneous description of a pushdown automaton. A
move from one instantaneous description to another will be denoted by the
symbol ; thus
is possible if and only if
Moves involving an arbitrary number of steps will be denoted by . The
expression
indicates a possible configuration change over a number of steps. 1
On occasions where several automata are under consideration we will use
M to emphasize that the move is made by the particular automaton M.
The Language Accepted by a Pushdown Automaton
Definition 7.2
Let M = (Q, Σ, Γ, δ, q 0 , z, F) be a nondeterministic pushdown automaton. The
language accepted by M is the set
In words, the language accepted by M is the set of all strings that can put M into
a final state at the end of the string. The final stack content u is irrelevant to this
definition of acceptance.
and u is the stack contents (with the leftmost symbol indicating the top of the
stack), is called an instantaneous description of a pushdown automaton. A
move from one instantaneous description to another will be denoted by the
symbol ; thus
is possible if and only if
Moves involving an arbitrary number of steps will be denoted by . The
expression
indicates a possible configuration change over a number of steps. 1
On occasions where several automata are under consideration we will use
M to emphasize that the move is made by the particular automaton M.
The Language Accepted by a Pushdown Automaton
Definition 7.2
Let M = (Q, Σ, Γ, δ, q 0 , z, F) be a nondeterministic pushdown automaton. The
language accepted by M is the set
In words, the language accepted by M is the set of all strings that can put M into
a final state at the end of the string. The final stack content u is irrelevant to this
definition of acceptance.