CSCI 338, Homework #5 Sample Solutions 3.2(d) - 3 points ------ q1 1 0 # 1 1 x q3 0 # 1 1 x 0 q3 # 1 1 x 0 # q5 1 1 x 0 q6 # x 1 x q7 0 # x 1 q7 x 0 # x 1 x q1 0 # x 1 x x q2 # x 1 x x # q4 x 1 x x # x q4 1 x x # x (1 or x) q-reject (or x x # x q-reject (1 or x)) 3.2 (e) - 1 point ------- q1 1 0 # 1 0 x q3 0 # 1 0 x 0 q3 # 1 0 x 0 # q5 1 0 x 0 q6 # x 0 x q7 0 # x 0 q7 x 0 # x 0 x q1 0 # x 0 x x q2 # x 0 x x # q4 x 0 x x # x q4 0 x x # q6 x x x x q6 # x x x q7 x # x x x x q1 # x x x x # q8 x x x x # x q8 x x x # x x q8 x x # x x b q-accept (b = blank) Turing Machine Simulator for Binary Number Counter - 4 points -------------------------------------------------- The machine was tested on the following five inputs: 0001 - desired result is 0010 1111 - desired result is 10000 1011 - desired result is 1100 1012 - desired result is :( 0 - desired result is 1 Ashley Bertrand's solution: ;Ashley Bertrand ;Homework 5 ;Question 3 ;If the input tape contains a binary number, this program finds the next higher binary number ;and halts in an accepting state. ;The machine replaces a non-binary number with ":(" and halts in a rejecting state. ;Initial input: string of 0's, 1's, and 2's ;Initial state: 0 ;State 0: ;If a 2 is read, proceed to state 2. ;Moves right until the end of the string is reached. ;Proceed to state 1. 0 _ _ l 1 0 0 0 r 0 0 1 1 r 0 0 2 2 r 2 ;State 1: ;If a 2 is read, proceed to state 2. ;Moves left changing 1's to 0's until a 0 or a "_" is read, which each get changed to a 1. ;Halt in an accepting state. 1 _ 1 l halt-accept 1 0 1 l halt-accept 1 1 0 l 1 1 2 2 r 2 ;State 2: ;Moves right until the end of the string is reached. ;Proceed to state 3. 2 _ _ l 3 2 0 0 r 2 2 1 1 r 2 2 2 2 r 2 ;State 3: ;Moves left until the end of the string is reached, replacing all symbols with "_". ;When the string is made up of only _'s, write a ":" and proceed to state 4. 3 _ : r 4 3 0 _ l 3 3 1 _ l 3 3 2 _ l 3 ;State 4: ;Write a "(". ;Halt in a rejecting state. 4 _ ( r halt-reject Problem #4 - 1 point ---------- d(q1, #) = (q2, #, R) Note: q1 is start state, d = delta d(q2, 0) = (q-ZERO, b, R) d(q2, b) = (q-BLANK, b, R) d(q-ZERO, 0) = (q-ZERO, 0, R) d(q-ZERO, b) = (q-BLANK, 0, R) d(q-ZERO, #) = (q3, 0, R) d(q-BLANK, 0) = (q-ZERO, b, R) d(q-BLANK, b) = (q-BLANK, b, R) d(q-BLANK, #) = (q3, b, R) d(q3, b) = (q4, #, L) d(q4, b) = (q4, b, L) d(q4, 0) = (q4, 0, L) d(q4, #) = (q-ACCEPT, #, L) 3.5 (d) - 1 point ------- No. Every Turing Machine has at least 2 states; q-accept and q-reject.