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


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 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.

Valid XHTML 1.0!