9. Let L be a pushdown automaton with tape alphabet A, and let u E A*. An infinite sequence a l ' a2, . of u-configurations for Lis if for some n and some x such that an infinite u-computation by L u = xy for some y, each finite sequence a l ' .. ' an' ... ' an +m' m ~ 0, is an x-computation by L. It is an accepting infinite u-computation if a 1 , , ak is an accepting u-computation by L for some k. (a) Give a pushdown automaton L 1 and word u 1 such that there is a nonaccepting infinite u-computation by L 1 (b) Give a pushdown automaton .L2 and word u 2 such that there is an accepting infinite u 2-computation (/1 , P1> y 1 ), (/2 , p 2 , y 2 ), ... by .L2 where, for some k, p 1 is an accepting state for all I~ k. (c) Give a pushdown automaton L 3 and word u3 such that there is an accepting infinite u 3-computation (/1 , p 1 , y 1 ), (/2 , p 2 , y 2 ), ... by .L3 where there is no k such that p 1 is an accepting state for all I ~ k.

10. Give the incompatible pairs among the following transitions. In each case, give the condition(s) 1, 2, 3, or 4 by which the pair is incompati ble. 8. Pushdown Automata qiaJI: Oqi qibJI: Oqi qiaJI: Oqz qiaO: lzqi q 1011 : Oqi

LetT= {a, b}, P = {~, ~ ,~,~}, 0. = {11 , 12}. We will write(,),[,] for ~,~,~,~,respectively. Give Y;(w), 1 :::;; i:::;; lwl + 1, for each of the following. (a) w = a(b[ba]a)b[a]. (b) w = (ab[ab)a]. {c) w = a[b ]]a. (d) w = (a([b ]a). 12. Let f be the grammar with productions S ~ SS, S ~a. (a) Use the construction in the proof of Theorem 8.2 to give a deterministic pushdown automaton that accepts L(f.). {b) Use the construction in the proof of Theorem 8.3 to give a pushdown automaton that accepts L(f). 13. (a) For pushdown automata L 1 , L 2 , L 3 in the examples, use the construction in the proof of Theorem 8.5 to give atomic push down automata ~ , L 2 , L 3 (b) Answer Exercise 2 for ~ , .ii2 , ~. 14. Let L be the pushdown automaton with Q = {q 1 , q 2}, initial state q 1 , F = {q2}, tape alphabet {a, b}, pushdown alphabet {A}, and transi tions q 1a0: Oq 1 q 1b0: Oq 2 q 100: Aq 1 q 10A: Oq 1 q 2 a0: Oq 1 q 2 b0: Oq2 q 20A: Oq2 q200: Aq2

Use the constructions in Theorems 8.6 and 5.4 to give a context-free grammar f such that L(f) = L(L). 15. Let us call a generalized pushdown automaton a device that functions just like a pushdown automaton except that it can write any finite sequence of symbols on the stack in a single step. Show that, for every generalized pushdown automaton L, there is a pushdown automaton .ii such that L(L) = L(.ii). 16.* Let 321 322 Chapter 1 0 Context-Free Languages be a set of dominoes on the alphabet A. Let B = {c1, ... , ck} be an alphabet such that A n B = 0. Let c $. A u B. Let R = {ycyR I y E A*B*}, L 1 = {u.u. lt l2 u.c.c. ln ln 'n-1 c. c.} l2 l t ' L 2 = {u. V 11 12 V C C 1n 1n 1n-l C C} 12 11 '