Introduction to Automata Theory, Languages, and Computation

Solutions for Chapter 8

Solutions for Section 8.2

Solutions for Section 8.3

Solutions for Section 8.4

Solutions for Section 8.5

Solutions for Section 8.1

Exercise 8.1.1(a)

1. Never halts unless we explicitly want it to, and

2. Halts whenever it prints hello, world.

For (1), we can add a loop such as while(1){x=x;} to the end of main, and also at any point where main returns. That change catches the normal ways a program can halt, although it doesn't address the problem of a program that halts because some exception such as division by 0 or an attempt to read an unavailable device. Technically, we'd have to replace all of the exception handlers in the run-time environment to cause a loop whenever an exception occurred.

For (2), we modify P to record in an array the first 12 characters printed. If we find that they are hello, world., we halt by going to the end of main (past the point where the while-loop has been installed).

Return to Top

Solutions for Section 8.2

Exercise 8.2.1(a)

[q0]00 |- X[q1]0 |- X0[q1]

The TM halts at the above ID.

Exercise 8.2.2(a)

In explanation, the TM makes repeated excursions back and forth along the tape. The symbols X and Y are used to replace 0's and 1's that have been cancelled one against another. The difference is that an X guarantees that there are no unmatched 0's and 1's to its left (so the head never moves left of an X), while a Y may have 0's or 1's to its left.

Initially in state q0, the TM picks up a 0 or 1, remembering it in its state (q1 = found a 1; q2 = found a 0), and cancels what it found with an X. As an exception, if the TM sees the blank in state q0, then all 0's and 1's have matched, so the input is accepted by going to state qf.

In state q1, the TM moves right, looking for a 0. If it finds it, the 0 is replaced by Y, and the TM enters state q3 to move left an look for an X. Similarly, state q2 looks for a 1 to match against a 0.

In state q3, the TM moves left until it finds the rightmost X. At that point, it enters state q0 again, moving right over Y's until it finds a 0, 1, or blank, and the cycle begins again.

Exercise 8.2.4

For part (a), given an input [x,y] use a second track to simulate the TM for f on the input x. When the TM halts, compare what it has written with y, to see if y is indeed f(x). Accept if so.

For part (b), given x on the tape, we need to simulate the TM M that recognizes the graph of f. However, since this TM may not halt on some inputs, we cannot simply try all [x,i} to see which value of i leads to acceptance by M. The reason is that, should we work on some value of i for which M does not halt, we'll never advance to the correct value of f(x). Rather, we consider, for various combinations of i and j, whether M accepts [x,i] in j steps. If we consider (i,j) pairs in order of their sum (i.e., (0,1), (1,0), (0,2), (1,1), (2,0), (0,3),...) then eventually we shall simulate M on [x,f(x)] for a sufficient number of steps that M reaches acceptance. We need only wait until we consider pairs whose sum is f(x) plus however many steps it takes M to accept [x,f(x)]. In this manner, we can discover what f(x) is, write it on the tape of the TM that we have designed to compute f(x), and halt.

Now let us consider what happens if f is not defined for some arguments. Part (b) does not change, although the constructed TM will fail to discover f(x) and thus will continue searching forever. For part (a), if we are given [x,y], and f is not defined on x, then the TM for f will never halt on x. However, there is nothing wrong with that. Since f(x) is undefined, surely y is not f(x). Thus, we do not want the TM for the graph of f to accept [x,y] anyway.

Exercise 8.2.5(a)

Return to Top

Solutions for Section 8.3

Exercise 8.3.3

Now, we can use this subroutine in a TM that starts in state q0. If this TM ever sees the blank, it accepts in state qf. However, whenever it is in state q0, it knows only that it has not seen a 1 immediately to its right. If it is scanning a 0, it must check (in state q5) that it does not have a blank immediately to its right; if it does, it accepts. If it sees 0 in state q5, it comes back to the previous 0 and calls the subroutine to skip to the next non-0. If it sees 1 in state q5, then it has seen 01, and uses state q6 to check that it doesn't have another 1 to the right.

In addition, the TM in state q4 (the final state of the subroutine), accepts if it has reached a blank, and if it has reached a 1 enters state q6 to make sure there is a 0 or blank following. Note that states q4 and q5 are really the same, except that in q4 we are certain we are not scanning a 0. They could be combined into one state. Notice also that the subroutine is not a perfect match for what is needed, and there is some unnecessary jumping back and forth on the tape. Here is the remainder of the transition table.

Return to Top

Solutions for Section 8.4

Exercise 8.4.2(a)

Exercise 8.4.3(a)

Once the copying is done, retract the head of tape 2 to the left end of the 100 symbols. Then, continue moving right on tape 1, and at each cell guess either to continue moving right or to guess that the second copy of x begins. In the latter case, compare the next 100 symbols on tape 1 with the 100 symbols on tape 2. If they all match, then move right on tape 1 and accept as soon as a blank is seen.

Exercise 8.4.5

Part (b), doing the same thing deterministically, is trickier, since we might start off in the wrong direction and travel forever, never seeing the $. Thus, we have to oscillate, using left and right endmarkers X and Y, respectively, to mark how far we have traveled on a second track. Start moving one cell left and leave the X. Then, move two cells right and leave the Y. Repeatedly move left to the X, move the X one more cell left, go right to the Y, move it once cell right, and repeat.

Eventually, we shall see the $. At this time, we can move left or right to the other endmarker, erase it, move back to the end where the $ was found, erase the other endmarker, and wind up at the $.

Exercise 8.4.8(a)

Exercise 8.4.8(b)

Return to Top

Solutions for Section 8.5

Exercise 8.5.1(c)

Return to Top