Q is a finite set of internal states of the control unit,
Σ is the input alphabet,
Γ is a finite set of symbols called the stack alphabet,
δ : Q × (Σ ∪ {λ}) × Γ → set of finite subsets of Q × Γ* is the transition
function,
q 0 ∈ Q is the initial state of the control unit,
z ∈ Γ is the stack start symbol,
F ⊆ Q is the set of final states.
The complicated formal appearance of the domain and range of δ merits a
closer examination. The arguments of δ are the current state of the control unit,
the current input symbol, and the current symbol on top of the stack. The result
is a set of pairs (q, x), where q is the next state of the control unit and x is a string
that is put on top of the stack in place of the single symbol there before. Note
that the second argument of δ may be λ, indicating that a move that does not
consume an input symbol is possible. We will call such a move a λ-transition.
Note also that δ is defined so that it needs a stack symbol; no move is possible if
the stack is empty. Finally, the requirement that the elements of the range of δ be
a finite subset is necessary because Q × Γ* is an infinite set and therefore has
infinite subsets. While an npda may have several choices for its moves, this
choice must be restricted to a finite set of possibilities.
Example 7.1
Suppose the set of transition rules of an npda contains
If at any time the control unit is in state q 1 , the input symbol read is a, and the
symbol on top of the stack is b, then one of two things can happen: (1) the
control unit goes into state q 2 and the string cd replaces b on top of the stack, or
(2) the control unit goes into state q 3 with the symbol b removed from the top of
the stack. In our notation we assume that the insertion of a string into a stack is
done symbol by symbol, starting at the right end of the string.
Σ is the input alphabet,
Γ is a finite set of symbols called the stack alphabet,
δ : Q × (Σ ∪ {λ}) × Γ → set of finite subsets of Q × Γ* is the transition
function,
q 0 ∈ Q is the initial state of the control unit,
z ∈ Γ is the stack start symbol,
F ⊆ Q is the set of final states.
The complicated formal appearance of the domain and range of δ merits a
closer examination. The arguments of δ are the current state of the control unit,
the current input symbol, and the current symbol on top of the stack. The result
is a set of pairs (q, x), where q is the next state of the control unit and x is a string
that is put on top of the stack in place of the single symbol there before. Note
that the second argument of δ may be λ, indicating that a move that does not
consume an input symbol is possible. We will call such a move a λ-transition.
Note also that δ is defined so that it needs a stack symbol; no move is possible if
the stack is empty. Finally, the requirement that the elements of the range of δ be
a finite subset is necessary because Q × Γ* is an infinite set and therefore has
infinite subsets. While an npda may have several choices for its moves, this
choice must be restricted to a finite set of possibilities.
Example 7.1
Suppose the set of transition rules of an npda contains
If at any time the control unit is in state q 1 , the input symbol read is a, and the
symbol on top of the stack is b, then one of two things can happen: (1) the
control unit goes into state q 2 and the string cd replaces b on top of the stack, or
(2) the control unit goes into state q 3 with the symbol b removed from the top of
the stack. In our notation we assume that the insertion of a string into a stack is
done symbol by symbol, starting at the right end of the string.