Logic & Computation Turing Machine Homework 1

For this homework assignment, you will be designing Turing Machines that fulfill the provided Regular Expressions or commands. The problems are substantially easier than on the lab. 1. Design a Turing Machine with the alphabet {a, b, #} that simply replaces every "b" with a "#". This Turing Machine does not accept or reject the string, it simply replaces characters. 2. Design a Turing Machine with the alphabet {0, 1, 2} that simply replaces every "0" with a "1", and it accepts if it reads "2" in the string. It rejects if it gets to the end of the String without reading a character of "2" once. 3. Design a Turing Machine with the alphabet {a, b} that satisfies the given Regular Expression: a(a|b){3}b*a+ 4. Design a Turing Machine with the alphabet {0, 1} that moves to the right 3 times if it reads "1", and it moves once to the left if it reads "0". It accepts the String if it reaches the end of the String, which it should read "Σ". 5. Design a Turing Machine with the alphabet {0, 1} that checks to see if a String has an even number of 0's in it. If it doesn't, add an extra 0 at the end of the String to make it have an even number of 0's.