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 machine’s behavior).
Problem 38. Page 340 #97 (Just provide an algorithm that describes the machine’s 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 M’s behavior).
1