[SOLVED] algorithm theory COMS 331: Theory of Computing, Spring 2019 Homework Assignment 5

COMS 331: Theory of Computing, Spring 2019 Homework Assignment 5
Note: Problems 33-35 ask you to give formal descriptions of Turing machines. This means to pre- cisely define each component of M = (Q, , , , , , s, t, r). This includes providing a transition table for . For all other problems requiring you to design Turing machines, just provide an algo- rithm which describes the behavior of the machine. The algorithm should be similar in detail as Example 28.1 on page 211-212 of your textbook. Problems 36-38 can be found in your textbook Automata and Computability by Dexter Kozen.
Problem 33. Give the formal description for a Turing machine that accepts the language L = {w | w starts with a 1 and ends with a 0} and always halts. The Turing machine should use = {0, 1}.
Problem 34. Give the formal description for a Turing machine that accepts the language
L = {w |w contains the substring 010} and always halts. The Turing machine should use = {0, 1}.
Problem 35. Give the formal description for a Turing machine that accepts the language
L = {w |w = 1m01n m,n N} and always halts. The Turing machine should use = {0,1}.
Problem 36. Page 309 #1.
Problem 37. Page 340 #96 (Just provide an algorithm that describes the machines behavior).
Problem 38. Page 340 #97 (Just provide an algorithm that describes the machines behavior).
Problem 39. Prove that if languages A and B are decidable (recursive) then the language A B is also decidable.
Problem 40. Prove that every regular language is decidable. (Hint: Given an arbitrary DFA M, show how to construct a TM which simulates Ms behavior).
1