Problem Solving in Automata, Languages, and Complexity

322 COMPUTATIONAL COMPLEXITY

* 5. What is wrong if we use the following simpler algorithm to compute IVk

inthe proof of Theorem 6.36?

For each k, to compute A& we generate each configuration

ac E Cz one by one and, for each one, nondeterministically ver-

ify whether reach (p, a, Ic) (by machine Ml), and increments

the counter for IVk by one if reach(P, cq Ic) holds.

* 6. Recall, from Exercise 6 of Section 3.5, the notion of 2-stack PDA’s. Show

that each language accepted by a 2-stack PDA is a context-sensitive

language.