CSCI 338: Homework 6

Sample Solution

Problems 2 (3 points) and 4 (3 points) were chosen for careful grading.

Problems - The homework set is complete

1. Provide a high-level description of the Turing Machine algorithm that decides {w | w does not contain twice as many 0s as 1s} over the alphabet {0, 1}.
2. Problem 3.15, part (d), on page 189.
3. Problem 4.2 on page 211.
4. Problem 4.3 on page 211.
5. Problem 4.7 on page 211.
6. Problem 4.8 on page 211.

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 6 no later than 7:00 p.m. on Friday, April 8th. Late submissions receive no credit, but partial credit can be earned by making an ontime submission.