Introduction to Automata Theory, Languages, and Computation

Revised 5/2/01.

## Solutions for Section 9.1

### Exercise 9.1.1(a)

37 in binary is 100101. Remove the leading 1 to get the string 00101, which is thus w_37.

### Exercise 9.1.3(a)

Suppose this language were accepted by some TM M. We need to find an i such that M = M_{2i}. Fortunately, since all the codes for TM's end in a 0, that is not a problem; we just convert the specification for M to a code in the manner described in the section.

We then ask if w_i is accepted by M_{2i}? If so, then w_i is not accepted by M, and therefore not accepted by M_{2i}, which is the same TM. Similarly, if w_i is not accepted by M_{2i}, then w_i is accepted by M, and therefore by M_{2i}. Either way, we reach a contradiction, and conclude that M does not exist.

## Solutions for Section 9.2

### Exercise 9.2.2(a)

A(2,1) = A(A(1,1),0) [rule 4] = A(A(A(0,1),0),0) [rule 4] = A(A(1,0),0) [rule 1] = A(2,0) [rule 2] = 4 [rule 3].

### Exercise 9.2.3(a)

Let's keep i, the integer in unary, whose square we have most recently printed on the output tape, on tape 1, and keep i^2 on tape 2, also in unary. Initially, i = 0. Repeatedly do the following:

1. Add 1 to tape 1; now we have i+1 there.

2. Copy tape 1 to tape 2 twice, and remove one to change i^2 to i^2 + 2(i+1) - 1 = (i+1)^2.

3. Copy tape 2 to the output as a block of 0's and append a 1.

### Exercise 9.2.4

By symmetry, if we can prove L_1 is recursive, we can prove any of the languages to be recursive. Take TM's M_1, M_2,...,M_k for each of the languages L_1, L_2,...,L_k, respectively. Design a TM M with k tapes that accepts L_1 and always halts. M copies its input to all the tapes and simulates M_I on the ith tape. If M_1 accepts, then M accepts. If any of the other TM's accepts, M halts without accepting. Since exactly one of the M_i's will accept, M is sure to halt.

### Exercise 9.2.5

Note that the new language defined in the displayed text should be L'; it is different from the given language L, of course. Also, we'll use -L for the complement of L in what follows.

Suppose L' were RE. Then we could design a TM M for -L as follows. Given input w, M changes its input to 1w and simulates the hypothetical TM for L'. If that TM accepts, then w is in -L, so M should accept. If the TM for L' never accepts, then neither does M. Thus, M would accept exactly -L, which contradicts the fact that -L is not RE. We conclude that L' is not RE.

### Exercise 9.2.6(a)

To test whether an input w is in the union of two recursive languages L1 and L2, we design a TM to copy its input w onto a second tape. It then simulates the halting TM for L1 on one tape and the halting TM for L2 on the other. If either accepts, then we accept. If both halt without accepting, we halt without accepting. Thus, the union is accepted by a TM that always halts.

In the case where L1 and L2 are RE, do the same, and accept if either accepts. The resulting TM accepts the union, although it may not halt. We conclude that both the recursive languages and the RE languages are closed under union.

### Exercise 9.2.6(e)

Consider the case where L is RE. Design a NTM M for h(L), as follows. Suppose w is the input to M. On a second tape, M guesses some string x over the alphabet of L, checks that h(x) = w, and simulates the TM for L on x, if so. If x is accepted, then M accepts w. We conclude that the RE languages are closed under homomorphism.

However, the recursive languages are not closed under homomorphism. To see why, consider the particular language L consisting of strings of the form (M,w,c^i), where M is a coded Turing machine with binary input alphabet, w is a binary string, and c is a symbol not appearing elsewhere. The string is in L if and only if M accepts w after making at most i moves. Clearly L is recursive; we may simulate M on w for i moves and then decide whether or not to accept. However, if we apply to L the homomorphism that maps the symbols other than c to themselves, and maps c to epsilon, we find that h(L) is the universal language, which we called L_u. We know that L_u is not recursive.

## Solutions for Section 9.3

### Exercise 9.3.1

The property of languages ``contains all the palindromes'' is a nontrivial property, since some languages do and others don't. Thus, by Rice's theorem, the question is undecidable.

### Exercise 9.3.4(d)

We shall reduce the problem L_e (does a TM accept the empty language?) to the question at hand: does a TM accept a language that is its own reverse? Given a TM M, we shall construct a nondeterministic TM M', which accepts either the empty language (which is its own reverse), or the language {10} (which is not its own reverse). We shall make sure that if L(M) is empty, then L(M') is its own reverse (the emoty language, in particular), and if L(M) is not empty, then L(M') is not its own reverse. M' works as follows:

1. First, check that its input is 10, and reject if not.

2. Guess an input w for M.

3. Simulate M on w. If M accepts, then M' accepts its own input, 01.

Thus, if L(M) is nonempty, M' will guess some string M accepts and therefore accept 01. If L(M) is empty, then all guesses by M' fail to lead to acceptance by M, so M' never accepts 01 or any other string.

### Exercise 9.3.6(a)

After making m transitions (not m+1 as suggested by the hint), the TM will have been in m+1 different states. These states cannot all be different. Thus, we can find some repeating state, and the moves of the TM look like [q_0] |-* q |-* q |-* ..., where the central |-* represents at least one move. Note that we assume the tape remains blank; if not then we know the TM eventually prints a nonblank. However, if it enters a loop without printing a nonblank, then it will remain forever in that loop and never print a nonblank. Thus, we can decide whether the TM ever prints a nonblank by simulating it for M moves, and saying ``yes'' if and only if it prints a nonblank during that sequence of moves.

### Exercise 9.3.7(a)

We reduce the complement of L_u to this problem, which is the complement of the halting problem for Turing Machines. The crux of the argument is that we can convert any TM M into another TM M', such that M' halts on input w if and only if M accepts w. The construction of M' from M is as follows:

1. Make sure that M' does not halt unless M accepts. Thus, add to the states of M a new state p, in which M' runs right, forever; i.e., delta(p,X) = (p,X,R) for all tape symbols X. If M would halt without accepting, say delta(q,Y) is undefined for some nonaccepting state q, then in M', make delta(q,Y) = (p,Y,R); i.e., enter the right-moving state and make sure M' does not halt.

2. If M accepts, then M' must halt. Thus, if q is an accepting state of M, then in M', delta(q,X) is made undefined for all tape symbols X.

3. Otherwise, the moves of M' are the same as those of M.

The above construction reduces the complement of L_u to the complement of the halting problem. That is, if M accepts w, then M' halts on w, and if not, then not. Since the complement of L_u is non-RE, so is the complement of the halting problem.

### Exercise 9.3.8(a)

We'll show this problem not to be RE by reducing the problem of Exercise 9.3.7(a), the ``nonhalting'' problem to it. Given a pair (M,w), we must construct a TM M', such that M' halts on every input if and only if M does not halt on w. Here is how M' works:

1. Given an input x of length n, M' simulates M on w for n steps.

2. If during that time, M halts, then M' enters a special looping state [as discussed in the solution to Exercise 9.3.7(a)] and M' does not halt on its own input x.

3. However, if M does not halt on w after n steps, then M' halts.

Thus, M' halts on all inputs if and only if M does not halt on w. Since we proved in the solution to Exercise 9.3.7(a) that the problem of telling whether M does not halt on w is non-RE, it follows that the question at hand --- whether a given TM halts on all inputs --- must not be RE either.

### Exercise 9.3.8(d)

This language is the complement of the language of Exercise 9.3.8(a), so it is surely not recursive. But is it RE? We can show it isn't by a simple reduction from the nonhalting problem. Given (M,w), construct M' as follows:

1. M' ignores its own input and simulates M on w.

2. If M halts, M' halts on its own input. However, if M never halts on w, then M' will never halt on its own input.

As a result, M' fails to halt on at least one input (in fact, on all inputs) if M fails to halt on w. If M halts on w, then M' halts on all inputs.

## Solutions for Section 9.4

### Exercise 9.4.1(a)

There is no solution. First, a solution would have to start with pair 1, because that is the only pair where one is a prefix of the other. THus, our partial solution starts:

```     A: 01
B: 011
```
Now, we need a pair whose A-string begins with 1, and that can only be pair 3. The partial solution becomes

```     A: 0110
B: 01100
```
Now, we need a pair whose A-string begins with 0, and either pair 1 or pair 2 might serve. However, trying to extend the solution with pair 1 gives us:

```     A: 011001
B: 01100011
```

while extending by pair 2 yields:

```     A: 0110001
B: 0110010
```

In both cases, there is a mismatch, and we conclude no solution exists.

### Exercise 9.4.3

The problem is decidable by the following, fairly simple algorithm. First, if all the A-strings are strictly longer than their corresponding B-strings, then there is surely no solution. Neither is there a solution in the opposite case, where all the B-strings are strictly longer than their corresponding A-strings.

We claim that in all other cases, there is a solution. If any corresponding pair of strings are the same length, then they are identical, and so just that pair is a solution. The only possibility remains has at least one pair, say i, with the A-string longer than the B-string, say by m symbols, and another pair, say j, where the B-string is longer than the A-string, say by n symbols. Then i^nj^m, i.e., n uses of pair i followed by m uses of pair j is a solution. In proof, it is easy to check that both the A- and B-strings that result have the same length. Since there is only one symbol, these strings are therefore identical.

## Solutions for Section 9.5

### Exercise 9.5.1

Given an instance (A,B) of PCP, construct the grammar G_A as in the text. Also, construct a grammar G_{BR}, that is essentially G_B, but with the bodies of all productions reversed, so its language is the reverse of the language of G_B. Assume the start symbols of these grammars are A and B, they contain no variables in common, and that c is a terminal that does not appear in these grammars.

Construct a new grammar G with all the productions of G_A and G_{BR}, plus the production S -> AcB. Then a solution to the PCP instance yields a string y such that y is generated by G_A and y^R is generated by G_{BR}. Thus, G generates the palindrome ycy^R. However, any palindrome generated by G must have the c in the middle and thus implies a solution to the PCP instance, that is, a string y that appears in L(G_A) while y^R appears in L(G_{BR}) [and therefore y appears in L(G_B)].