Suppose that in Example 7.2 we replace the given value of (q2, , 0) with ( q 2 , , 0 ) = { ( q 0 , ) } . What is the language accepted by this new pda?

Example 7.2

\fWhat 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 o(qo, b, 0). The inter- pretation 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 6(q] , a, 1) = {(q, ,11)}, which adds a 1 to the stack when an a is read, and 8(92 , b, 1) = 1(92 , 1)}, 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, until the first b is encountered at which time it goes into state 92. This ensures that no b precedes the last a. After analyzing the remaining transitions, we see that the npda will end in the final state q; if and only if the input string is in the language L = {a" b" :n 20 } ulal. As an analogy with finite automata, we might say that the npda accepts the above language. Of course, before making such a claim, we must define what we mean by an npda accepting a language