CMSC 208
Spring 2017
04/19/2017
Turing Machines
Due: Monday, April 24
beginning of class (3pm)


For this assignment, you may work in pairs (no groups of 3 or more will be permitted).    
By putting more than one name on the assignment, you are stating that both people contributed significantly to each part.


Assignment:  (worth 15 exercise points )

Use JFlap to create the following Turing Machines:  (  NOTE:    Here, the _  will indicate the blank symbol for typography purposes.  Further, the read head will be indicated by a larger bold font.)

1)   A machine that determines if two input strings (separated by a single blank symbol) are identical.     An accepting state will give us our answer.  (Did we end in the accepting state or not?)

Input alphabet:  {x, y , z}
Tape alphabet:   {x, y , z}  plus blank symbol, plus any other characters you wish.

EG:
inputresult
_  _  x  y  x  y  z  _  x  y  x  y  z  _ accepted
_  _  x  y  x  x  z  _  x  y  x  y  z  _ not accepted
_  _  x  y  x  y  z  _  y  x  y  z  _ not accepted

The inputs may be munged as you see fit.




2)   A Turing Machine that computes   f(x)  =  x  mod 4

Input alphabet:  {1}
Tape alphabet:   {1}  plus blank symbol, plus any other characters you wish.

Input:   a non-negative integer represented in unary, read head at the beginning of the input, with at least one blank symbol on either end.

Result:   a non-negative integer represented in unary, read head at the beginning of the answer, with at least one blank symbol on either end.

Requirements:
i)  The input string must be totally removed from the tape, with at least one blank space between it and the answer.

EG:   input:   _ _ 1 1 1 1 1 1 1 1 1 1 _ _
         result:   _ _ _ _ _ _ 1 1 _ _ _

ii)  There should be a final state that indicates the calculation successfully completed and the tape has been set appropriately.



 3)   A Turing Machine that computes   f(x)  =  x  mod 4

Input alphabet:  {1}
Tape alphabet:   {1}  plus blank symbol, plus any other characters you wish.

Input:   a non-negative integer represented in unary, read head at the beginning of the input, with at least one blank symbol on either end.

Result:   a non-negative integer represented in unary, read head at the beginning of the answer, with at least one blank symbol on either end.

Requirements:
i)  The input string must be intact, with at least one blank space between it and the answer.

EG:   input:    _ _ 1 1 1 1 1 1 1 1 1 1 _ _
         result:   _ _ 1 1 1 1 1 1 1 1 1 1 _ _ 1 1 _ _

ii)  There should be a final state that indicates the calculation successfully completed and the tape has been set appropriately.


Handin:

There is a place in Canvas to submit each JFlap file.

If you work in a pair:
  • Choose one person to submit,and the other to not submit.
    • The "submit" person should submit the file via canvas AND put in the Canvas comments whom you worked with.
    • The "not submit" person should go to canvas and put in the Canvas comments whom you worked with.