# CS154 Assignment #5 Solutions

1. Let n be the pumping-lemma constant, and consider z = 0^n1^{n+1}2^{n+2}. We can write z = uvwxy such that |vwx| <= n and |vx| > 0. Note that vx is too short to consist of all three symbols, 0, 1, and 2, so these strings consist of at most two of the three.

(a)
If vx has no 2's, then uv^3wx^3y has at least 2n+3 0's and 1's, and therefore has to have at least n+2 of one of them. That symbol occurs at least as many times as do the 2's, so this string is not in L.

(b) If vx has 2's, it cannot have 0's. Then uwy has at most 2n+2 1's and 2's, and n 0's. If there are more than n 1's, then there cannot be more 2's than 1's. Either way, uwy is not in L.

2. One approach is a PDA construction. Given a PDA P for L, construct another PDA P' that simulates P, but insists that before reading any input symbol it must make (on epsilon input) a transition that P would make on input a. P' is like P with the following exceptions:

(a)
P' has an additional state q' for every state q of P. None of the new states are accepting.

(b)
The primed states have the same transitions on epsilon input as the corresponding unprimed states, but they go to a primed state. That is, if delta(q,epsilon,X) contains (p,gamma), then delta'(q',epsilon,X) contains (p',gamma). Note that this capability --- simulating as many epsilon-transitions as P makes before reading an a is essential.

(c)
The primed states can go, on epsilon, to whatever unprimed state P goes to on input a. That is, if delta(q,a,X) contains (p,gamma), then delta'(q',epsilon,X) contains (p,gamma).

To see why this works, suppose aw is in L. Then P' will simulate, with epsilon input, whatever P does until it makes a move that reads the a. From that point, P' can only simulate P, and thus accepts w if and only if P accepts aw.

3. Let n be the pumping-lemma constant. Pick m = n! + n. The algorithm is to test whether all strings of 0's of length up to m are in L. If not, then L does not contain all strings of 0's.

We must prove that if L does contain all these strings, then it contains every string of 0's. We could prove by induction on i that 0^{m+i} is in L for all i. However, an equivalent, and in this case easier, argument is a ``shortest counterexample'' argument.

Suppose that, although all strings of 0's of length up to m are in L, there is some string 0^k that is not. Then k > m, surely. Let k be the smallest integer with that property; i.e., all strings of 0's, from epsilon up to 0^{k-1} are in L. Consider 0^{k-n!}. Because k > n! + n, 0^{k-n!} is of length at least n. Thus, the pumping lemma applies to it, and we know that we can write 0^{k-n!} = uvwxy such that vx, of length between 1 and n, can be ``pumped.'' Since the length of vx surely divides n!, we know we can find some i, namely i = 1+n!/|vx|, such that uv^iwv^iy = 0^k. By the pumping lemma, it follows that 0^k really is in L after all. If there is no shortest string of 0's that is not in L, then there can be no string of 0's at all that is not in L; i.e., L contains all strings of 0's, if it contains all the strings up to 0^m.

4. Make the following modifications to P:

(a)
Change all variables named x to some new identifier that does not appear in P.

(b)
Replace all output statements by statements that store into an array the characters that would be printed, checking whether they are hello, world.

(c)
If we find that hello, world. would have been printed by P, then execute an assignment x=1;

The resulting program assigns to x if and only if P prints hello, world. If we could tell whether the new program assigns to x, we could tell whether the given program P was a hello, world. printer, which we know we cannot do. Thus, the hypothetical ``assign to x'' tester does not exist.

5. Let M = ({q,p,r},{a,b}, {a,b,B}, delta, q, B, {r}), where delta is given by:

• delta(q,a) = (q,a,R)
• delta(q,b) = (p,b,R)
• delta(q,B) = (r,B,R)
• delta(p,b) = (p,b,R)
• delta(p,B) = (r,B,R)

That is, q, the start state, says ``we have not yet seen a b''; state p says ``we have seen a b, but not yet reached a blank,'' and r is the accepting state, reached if we get to a blank after moving over 0 or more a's and 0 or more b's.