CSci 311: Models of Computation
CSci 500: Fundamental Concepts of Computing
Fall Semester 1999

Assignment #3
Due Wednesday, 15 September 1999

CSci 311 students do at least nine of the following exercises from the Linz textbook. CSci 500 students do all the following exercises.

Be sure to follow the directions given in the syllabus! For example, please write on one side of the paper only and staple papers in the proper order.

Section 2.1 exercises, pages 47-50.

• Exercise 2, part (b)
• Exercise 2, part (c)
• Exercise 7, part (c)
• Exercise 8, part (b).
  Suggestion: Use mnemonic labels for the states; the states can be named to reflect the "meaning" of being in that state in terms of the problem you are trying to solve. For example, the state name aa could mean that two a symbols have been read.
• Exercise 12

Section 2.2 exercises, pages 56-7.

• Exercise 2
• Exercise 4
• Exercise 8
• Exercise 9

Section 2.3 exercises, pages 64-5.

• Exercise 3