CS154 Assignment #6 Solutions

1. Think of the positions of M_2's tape as ...X_{-2}X_{-1}X_0X_1X_2..., where X_0 is the contents of the cell at which the head is initially placed. Then the tape of M_1 will have two tracks. The leftmost cell will hold X_0 in the upper track and a special marker * in the lower track. Other cells will hold X_i in the upper track and X_{-i} in the lower track. We identify input symbol a with the pair [a,B].

   The state of M_1 will have states of the form [q,U] (M_2 is in state q and working on the upper track) and [q,L] (M_2 is working on the lower track in state q). M_1 will have a special start state [q_0,S], where q_0 is the start state of M_2; its role is to place the special marker * on the first cell of the lower track, as well as simulating q_0 on the upper track. The rules of delta are:

   • If delta_2(q,X) = (p,Y,R) then:
     1. delta_1([q,U],[X,Z]) = ([p,U],[Y,Z],R) for all tape symbols Z. I.e., if M_2 is at or to the right of its initial position, simulate it on the upper track.
     2. delta_1([q,L],[Z,X]) = ([p,L],[Z,Y],L) for all Z. I.e., if M_2 is to the left of its initial position, simulate it, but in reverse.
     3. delta_1(q,L),[X,*]) = ([p,U],[Y,*],R). Here, M_1 has simulated M_2 moving from the left, back to its original position. M_1 thinks it is working on the lower track, but needs to switch to the upper.
     4. In addition, if q = q_0, then delta_1([q_0,S],[X,B]) = ([p,U],[Y,*],R).

   • If delta_2(q,X) = (p,Y,L) then:
     1. delta_1([q,U],[X,Z]) = ([p,U],[Y,Z],L) for all tape symbols Z. I.e., if M_2 is at or to the right of its initial position, simulate it on the upper track.
     2. delta_1([q,L],[Z,X]) = ([p,L],[Z,Y],R) for all Z, including *. I.e., if M_2 is to the left of its initial position, simulate it, but in reverse.
     3. delta_1(q,U),[X,*]) = ([p,L],[Y,*],R). Here, M_1 has simulated M_2 moving from the right, back to its original position. M_1 thinks it is working on the upper track, but needs to switch to the lower.
     4. In addition, if q = q_0, then delta_1([q_0,S],[X,B]) = ([p,L],[Y,*],R).

2. As you read the 0's, increment two different counts for each 0. When 1's come in, leave the first of these counters fixed, and decrement the second counter, once for each 1. Then, when 2's come in, decrement the second counter once for each 2. If both counters are 0, accept; otherwise, don't. Hmm... that only used two counters. I wonder what we need the third for?

3. For (a), P is a nontrivial property of the RE languages, so by Rice's Theorem, it is undecidable.

   Now, consider (b). We show that -P (our HTML representation of the complement of P) is RE. Then, if P were RE, it would be recursive, which it is not. To show -P is RE, we design a 102-tape nondeterministic TM to accept it. Every invalid TM code is deemed to represent a TM that accepts (0+1)*, and therefore will accept at least 101 strings and be in -P. The first step for our NTM is to check that the input TM code is valid, and accept if not.

   Otherwise, the NTM guesses 101 strings and simulates its input TM on each of them, ``in parallel.'' If all are accepted, the NTM accepts its own input.

4. (a) Yes; 1,2,3,1 is an example of a solution.

   (b) No. There are many possible arguments. Here's one. First, there can be no solution that consists of index 1's only, because the B (second list) string will be longer than the A (first list) string. If there is a solution with only 1,'s and 3's, then it can't use 3's, because the third pair has a 0 in the A string and there is no way to get a matching 0 in the B string. Since we already know index 1 alone is not enough for a solution, we know that 1 and 3 alone is not enough. Thus, if there is a solution, it must use pair 2. But then, the solution string has 00 somewhere. But no string composed from the A-list strings can have 00, since the only 0 (in w_3) is followed by 1. Thus, there is no solution.

5. Let S be the start symbol of G. Grammar H consists of all the productions of G, plus a new start symbol T, a new terminal a, and the production T -> SaSaSaSaSaSaS. If G has a string w with two different parse trees, then we can use the production above at the root to get 2^7 = 128 different parse trees for wawawawawawaw. Thus, if G is ambiguous, H is superambiguous.

   Conversely, suppose G is unambiguous. Let x = w_1aw_2aw_3aw_4aw_5aw_6aw_7 be a string in L(H). Because a is a symbol that appears only in the introduced production, it must be that each w_i is in L(G). Thus, each w_I has a unique leftmost derivation, and the only leftmost derivation of x must begin with a use of production T -> SaSaSaSaSaSaS, followed, by a leftomost derivation of w_1, then a leftmost derivation of w_2, and so on. We conclude that if G is unambiguous, then H must be unambiguous, and thus surely not superambiguous.

   Note that the use of a to separate strings derived from S is essential. Otherwise, we could have an unambiguous grammar like S -> epsilon | b | bb. If we simply used T -> SSSSSSS as the new production for H, a string like bbbbbbb would have hundreds of parse trees. While we might use S -> b seven times to derive bbbbbbb, we could also use it five times, use S -> epsilon once and S -> bb once, yielding 42 different parse trees. We could also use S -> b only three times, yielding 210 more parse trees, or only once, yielding 140 more.