that the npda will end in the final state q 3 if and only if the input string is in the
language
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.
We can also use transition graphs to represent npda's. In this representation
we label the edges of the graph with three things: the current input symbol, the
symbol at the top of the stack, and the string that replaces the top of the stack.
Example 7.3
The npda in Example 7.2 is represented by the transition graph in Figure 7.2.
Figure 7.2
While transition graphs are convenient for describing npda's, they are less
useful for making arguments. The fact that we have to keep track, not only of the
internal states, but also of the stack contents, limits the usefulness of transition
graphs for formal reasoning. Instead, we introduce a succinct notation for
describing the successive configurations of an npda during the processing of a
string. The relevant factors at any time are the current state of the control unit,
the unread part of the input string, and the current contents of the stack. Together
these completely determine all the possible ways in which the npda can proceed.
The triplet