Introduction to Automata Theory, Languages, and Computation

Solutions for Chapter 9

Revised 5/2/01.

Solutions for Section 9.1

Solutions for Section 9.2

Solutions for Section 9.3

Solutions for Section 9.4

Solutions for Section 9.5

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 w37.

Exercise 9.1.3(a)

Suppose this language were accepted by some TM M. We need to find an i such that M = M2i. 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 wi is accepted by M2i? If so, then wi is not accepted by M, and therefore not accepted by M2i, which is the same TM. Similarly, if wi is not accepted by M2i, then wi is accepted by M, and therefore by M2i. Either way, we reach a contradiction, and conclude that M does not exist.

Return to Top

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 i2 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 i2 to i2 + 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 L1 is recursive, we can prove any of the languages to be recursive. Take TM's M1, M2,...,Mk for each of the languages L1, L2,...,Lk, respectively. Design a TM M with k tapes that accepts L1 and always halts. M copies its input to all the tapes and simulates MI on the ith tape. If M1 accepts, then M accepts. If any of the other TM's accepts, M halts without accepting. Since exactly one of the Mi'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,ci), 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 ε, we find that h(L) is the universal language, which we called Lu. We know that Lu is not recursive.

Return to Top

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)

Revised 7/19/05

We shall reduce the problem Le (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 {01} (which is not its own reverse). We shall make sure that if L(M) is empty, then L(M') is its own reverse (the empty 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 01, 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 [q0] |-* 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 Lu 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., δ(p,X) = (p,X,R) for all tape symbols X. If M would halt without accepting, say δ(q,Y) is undefined for some nonaccepting state q, then in M', make δ(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', δ(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 Lu 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 Lu 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.

Return to Top

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 injm, 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.

Return to Top

Solutions for Section 9.5

Exercise 9.5.1

Given an instance (A,B) of PCP, construct the grammar GA as in the text. Also, construct a grammar GBR, that is essentially GB, but with the bodies of all productions reversed, so its language is the reverse of the language of GB. 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 GA and GBR, plus the production S -> AcB. Then a solution to the PCP instance yields a string y such that y is generated by GA and yR is generated by GBR. Thus, G generates the palindrome ycyR. 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(GA) while yR appears in L(GBR) [and therefore y appears in L(GB)].

Return to Top