CSCI 338: Homework 5
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
- Problem 3.2, part (d) on page 187.
- Problem 3.2, part (e) on page 187.
- 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.
- 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#.
- Problem 3.5, part d, on page 188.
Grading - 10 Points
- To earn points, your answers must be easily readable.
- You will earn 1 point per problem for a reasonable looking
solution.
- At least one problem will be selected for careful grading. The
rest of the 10 points will be allocated to these problems.
- Solutions to all problems will be posted.
Partners
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.
Submission
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.