Definitions Given a language L , we define the following two-player pumping games. In both games, the winner is the last player to make a legal move. So if they finish the game, N wins.

Regular Pumping Game for L: 1. R chooses an integer p 0.

2. N chooses a string s L such that |s| p.

3. R chooses strings x, y, z such that s = xyz, |xy| p, and |y| > 0.

4. N chooses an integer i 0 such that xyiz L.

Pumping Claim 1: If L is regular, then R has a winning strategy. (Chapter 1 pumping lemma.)

Context-Free Pumping Game for L: 1. C chooses an integer p 0.

2. N chooses a string s L such that |s| p.

3. C chooses strings u, v, x, y, z such that s = uvxyz, |vxy| p, and |vy| > 0.

4. N chooses an integer i 0 such that uvixyiz L. Pumping Claim 2: If L is context-free, then C has a winning strategy. (Chapter 2 pumping lemma.) Roughly speaking: N tries to pick a a unpumpable string s, while R (or C) tries to find a pumpable substring (or pair of substrings) in s. We often use the above pumping claims in the contrapositive direction: If N has a winning strategy for the regular game, then L is not regular.

If N has a winning strategy for the context-free game, then L is not context-free.

question:

We are given a PDA P. From Chapter 2, we know there is an equivalent CNF grammar G.

(a). Lookup shift-reduce parser on wikipedia (also known as bottom-up). Using that, construct a PDA P 0 accepting L(G). You do not have to give P 0 as a tuple, just a generic description and diagram of P 0 (like Sipsers parser) is enough. (Unlike Sipsers parser, for this one it is easier to imagine the stack is a string, and the top is the right end of the string.)

(b). Argue that on an input of length n, any computation of P 0 (accepting or not) takes at most O(n) steps. (Remark: this problem shows that we can convert a PDA to an equivalent PDA that always stops within O(n) steps.)