7. Show that the pushdown automaton in Example 7.4 is not deterministic, but that the language in the example is nevertheless deterministic. Construct an npda for the language L={w{a,b}:na(w)=nb(w)} As in Example 7.2, the solution to this problem involves counting the number of a 's and b 's, which is easily done with a stack. Here we need not even worry about the order of the a 's and b 's. We can insert a counter symbol, say 0 , into the stack whenever an a is read, then pop one counter symbol from the stack when a b is found. The only difficulty with this is that if there is a prefix of w with more b 's than a 's, we will not find a 0 to use. But this is easy to fix; we can use a negative counter symbol, say 1 , for counting the b 's that are to be matched against a 's later. The complete solution is given in the transition graph in Figure 7.3. a,0,00;b,1,11a,z,0z;b,0,b,z,12;a,1, FIGURE 7.3 In processing the string baab, the npda makes the moves (q0,baab,z)(q0,aab,1z)(q0,ab,z)(q0,b,0z)(q0,,z)(qf,,z) and hence the string is accepted