CSE 3502, Homework 6

Creating TM programs
due 11/1/17 by email


For this homework, you will write programs (specifications) for four TMs and run them using a TM simulator. We will use a Turing Machine simulator available here: http://morphett.info/turing/turing.html .  The instructions for it are lower on the same web page. 

1.      Make the programs as short and easy to read as possible, with good state names and comments.

2.      Test your programs over multiple inputs, both those that should be accepted and those that should be rejected. 

3.      Make sure the comments for each program have your name and the name and description of the machine.

4.      Put these three specifications into a single TEXT (ASCII file) called hwk6-Your-Name, and email it to Professor Goldin before class, with CC to TA Anna Gorbenko.

Part 0: warmup

There are several example TM programs available on that web page.  Run some of them on various inputs to understand how this machine works.  Then write the program for the Turing Machine M1 in example 3.9 based on the diagram in Figure 3.10 , and make sure it works correctly.

Part 1: modifying M1
Let Labcd be the following language:
Labcd = {wu: w is a string over {a,b}, u is a string over {c,d}, and if if we replace all a's in w by c'd and all b's by d's, we get u}
Example: “aabbaccddc” is in Labcd, because “aabba” = “ccddc” up to replacement of a's by c'd and b's by d's
Your job is to modify your M1 from warmup, and create a Turing Machine Mabcd which recognizes Labcd , .
Note: Make sure Mabcd rejects all strings that are not in Labcd such as odd-length strings or strings that have c/d preceding a/b.

Part 2: TM Computing functions from strings to strings.
Create a program for TM M01 that does the following: given a string w over alphabet {0,1}, in the first half of w, it replaces all the 0's by a's and 1's by b's. In the 2nd half of w, it replaces all the 0's by c's and 1's by d's.
This program will accept ALL strings of 0's and 1's, replace all 0's and 1's as described, and will always terminate with the head on the LEFTMOST tape cell.
Example: if the input string is “011101”, the output string is “abbdcd” with the head over 'a'
Except when necessary, do not use any of the same names for the states of M01 as for the states of Mabcd
Note: this is an example of a machine which computes a function; in this case, it's a function from strings to strings.

Part 3: Combing two TM programs into one
Now append together the programs of the two machines M01 and Mabcd, to obtain a new Turing Machine M01abcd which first replaces all 0's by a/c and all 1's by b/d and then determines if the resulting string is in Labcd
Note: If you created M01 and Mabcd correctly, then the only thing you have to do here is to make the accept state of M01 be the same the (former) initial state of Mabcd
Example: if input is 011101, it will first be transformed to abbdcd, and then it will be REJECTED.
In your comments for M01abcd , indicate what language this machine accepts, making the description of this language as simple as possible. Hint: this language is simple to describe.