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:
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.
(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.
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.