# CSCI 338: Homework 6

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

## Problems - The homework set is complete

- 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}.
- Problem 3.15, part (d), on page 189.
- Problem 4.2 on page 211.
- Problem 4.3 on page 211.
- Problem 4.7 on page 211.
- 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.