CSCI 338: Homework 5

Sample Solution

The problems selected for careful grading were 3.2(d), worth 3 points and the Turing Machine Simulator, worth 4 points.

Problems - This homework set is complete

  1. Problem 3.2, part (d) on page 187.
  2. Problem 3.2, part (e) on page 187.
  3. Write a program for this Turing Machine Simulator. Assume Σ = {0, 1, 2}. If the tape contains a binary number (such as 0100), the Turing Machine should replace the tape with the next higher binary number (0101 in this case) and enter an accepting state. If the tape contains a non-binary number (such as 0120), the original input should be replaced with the frowny face (e.g. ":(") and the machine should enter a rejecting state. Submission Note: To earn points for this answer, place your solution in a .txt file and upload it separately from the answers to the other problems. This allows your solution to be copied and pasted into the Turing Machine Simulator for testing.
  4. Assume that Γ for a standard Turing Machine is {0, #, b} where b is the blank symbol, # appears twice (once at the far left and once at the end of the input), and the machine starts in state q0 with the read/write head positioned on the left most cell of the tape. Show the transitions needed to add a blank symbol one position to the right of the leftmost # and to shift the rest of the contents of the tape one cell to the right. The read/write head should finish on the leftmost # symbol and the machine should finish in state qaccept. Your solution should be a series of transitions in the following form
      δ(qi, tape-symbol) = (qj, tape-symbol, L or R)
    Solve the problem using as few transitions as possible. Example: if the input tape starts with #00b00#, it should end with #b00b00#.
  5. Problem 3.5, part d, on page 188.

Grading - 10 Points


You may work alone or you may partner with one classmate. If you work with a partner, submit only one solution with both of your names on it.


Upload your submission to the D2L Dropbox for Homework 5 no later than 7:00 p.m. on Friday, April 1st. Late submissions receive no credit, but partial credit can be earned by making an ontime submission.

Valid XHTML 1.0!