Example 7.2
Consider an npda with
with initial state q 0 and
What can we say about the action of this automaton?
First, notice that transitions are not specified for all possible combinations of
input and stack symbols. For instance, there is no entry given for δ (q 0 , b, 0). The
interpretation of this is the same that we used for nondeterministic finite
automata: An unspecified transition is to the null set and represents a dead
configuration for the npda.
The crucial transitions are
which adds a 1 to the stack when an a is read, and
which removes a 1 when a b is encountered. These two steps count the number
of a’s and match that count against the number of b’s. The control unit is in state
q 1 until the first b is encountered at which time it goes into state q 2 . This assures
that no b precedes the last a. After analyzing the remaining transitions, we see
Consider an npda with
with initial state q 0 and
What can we say about the action of this automaton?
First, notice that transitions are not specified for all possible combinations of
input and stack symbols. For instance, there is no entry given for δ (q 0 , b, 0). The
interpretation of this is the same that we used for nondeterministic finite
automata: An unspecified transition is to the null set and represents a dead
configuration for the npda.
The crucial transitions are
which adds a 1 to the stack when an a is read, and
which removes a 1 when a b is encountered. These two steps count the number
of a’s and match that count against the number of b’s. The control unit is in state
q 1 until the first b is encountered at which time it goes into state q 2 . This assures
that no b precedes the last a. After analyzing the remaining transitions, we see