Hw6sols.pdf

CS 162

Fall 2015

Homework 6 Solutions November 10, 2015

Timothy Johnson

1. Exercise 8.2.1(b) on page 335 of Hopcroft et al. Show the ID’s of the Turing machine of Figure 8.9 if the input tape contains 000111.

State q0 q1 q2 q3 q4

0 (q1 , X, R) (q1 , 0, R) (q2 , 0, L) -

1 (q2 , Y, L) -

Symbol X (q0 X, R) -

Y (q3 , Y, R) (q1 , Y, R) (q2 , Y, L) (q3 , Y, R) -

1

B (q4 , B, R) -

q0 000111 ` Xq1 00111 ` X0q1 0111 ` X00q1 111 ` X0q2 0Y 11 ` Xq2 00Y 11 ` q2 X00Y 11 ` Xq0 00Y 11 ` XXq1 0Y 11 ` XX0q1 Y 11 ` XX0Y q1 11 ` XX0q2 Y Y 1 ` XXq2 0Y Y 1 ` Xq2 X0Y Y 1 ` XXq0 0Y Y 1 ` XXXq1 Y Y 1 ` XXXY q1 Y 1 ` XXXY Y q1 1 ` XXXY q2 Y Y ` XXXq2 Y Y Y ` XXq2 XY Y Y ` XXXq0 Y Y Y ` XXXY q3 Y Y ` XXXY Y q3 Y ` XXXY Y Y q3 B ` XXXY Y Y Bq4 B Since we’ve reached the final state q4 , the string is accepted. 2. Exercise 8.2.2(c) on page 336 of Hopcroft et al. Design a Turing machine that accepts the language {wwR |w is any string of 0’s and 1’s}. We cross off the first character in the string. (If the input is empty, we accept, because this is in our language when w = .) Then we scan to the end of the string and check if the last character matches the first one. If it does not match, the machine crashes. If it does match, we cross it off and return to the beginning to check the second character of the string. We repeat until every character has been crossed off, at which point we accept. 2

Our transition function is defined as follows, where q6 is the final state: State q0 q1 q2 q3 q4 q5 q6

0 (q1 , X, R) (q1 , 0, R) (q2 , 0, R) (q5 , Y, L) (q5 , 0, L) -

1 (q2 , X, R) (q1 , 1, R) (q2 , 1, R) (q5 , Y, L) (q5 , 1, L) -

Symbol X (q0 , X, R) -

Y -

B (q6 , B, R) (q3 , B, L) (q4 , B, L) -

3. Exercise 8.2.3 on page 336 of Hopcroft et al. Design a Turing machine that takes as input a number N and adds 1 to it in binary. To be precise, the tape initially contains a $ followed by N in binary. The tape head is initially scanning the $ in state q0 . Your TM should halt with N + 1, in binary, on its tape, scanning the leftmost symbol of N + 1, in state qf . You may destroy the $ in creating N + 1, if necessary. For instance, q0 $10011 `∗ $qf 10100, and q0 $11111 `∗ qf 100000. First we scan to the end of our input. Then if we see a 0, we change it to 1. If we see a 1, we change it to 0, and carry to the next digit. Eventually either we will reach a zero, or we will reach the $ at the beginning. If we reach a zero, we change it to 1 and stop. If we reach the $ at the beginning, we change it to 1 and stop. Our transition function is as follows, where q2 is the final state: State q0 q1 q2

0 (q0 , 0, R) (q2 , 1, R) -

Symbol 1 (q0 , 1, R) (q1 , 0, L) -

$ (q0 , $, R) (q2 , 1, R) -

B (q1 , B, L) -

4. Exercise 8.4.2(b) on page 350 of Hopcroft et al. Here is the transition function of a nondeterministic TM, M = ({q0 , q1 , q2 }, {0, 1}, {0, 1, B}, δ, q0 , B, {q2 }) : δ q0 q1 q2

0 {(q0 , 1, R} {(q1 , 0, R), (q0 , 0, L)} ∅

1 {(q1 , 0, R)} {(q1 , 1, R), (q0 , 1, L)} ∅

B ∅ {(q2 , B, R)} ∅

Show the ID’s reachable from the initial ID if the input is 011. We can do either a breadth-first or depth-first search to find all of the reachable ID’s. I choose to do a breadth-first search, which gives us the ID’s in the following order:

3

• q0 011 • 1q0 11 • 10q1 1 • 101q1 B • 1q0 01 • 101Bq2 B • 11q0 1 • 110q1 B • 110Bq2 B 5. Exercise 8.4.6 on page 351 of Hopcroft et al. Design the following 2-tape TM to accept the language of all strings of 0’s and 1’s with an equal number of each. The first tape contains the input, and is scanned from left to right. The second tape is used to store the excess of 0’s over 1’s, or vice-versa, in the part of the input seen so far. Specify the states, transitions, and the intuitive purpose of each state. We will scan from left to right on our first tape. In state q1 , the position on the second tape stores the number of extra 0’s we have seen. In state q2 , the position on the second tape stores the number of extra 1’s we have seen. State q3 is our final state. We begin by writing an extra $ symbol on the second tape, to mark when it is empty. We know we have read all of our input when we reach a blank symbol on the first tape. Our transition function is as follows. δ q0 q1 q2 q3

0,B (q1 , B, R, $, R) (q1 , B, R, B, R) (q2 , B, R, B, L) -

1,B (q2 , B, R, $, R) (q1 , B, R, B, L) (q2 , B, R, B, R) -

B,B (q3 , B, R, $, R) -

4

0,$ (q1 , B, R, $, R) (q1 , B, R, $, R) -

1,$ (q2 , B, R, $, R) (q2 , B, R, $, R) -

B,$ (q3 , B, R, $, R) (q3 , B, R, $, R) -