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

Assignment #2
Due Tuesday, 22 September 2015

CSci 311 students do at least nine of the following exercises from the Linz textbook. CSci 500 students do all of 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-9.

• Exercise 2, part (a)
• Exercise 2, part (d)
• Exercise 7, part (e)
• Exercise 8, part (a).
  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 11

Section 2.2 exercises, pages 54-6.

• Exercise 2
• Exercise 7
• Exercise 12
• Additional exercise. Find an nfa for the language consisting of the set of strings over {a,b} whose third-to-the-last symbol is b. For example, aababaa and abba are in the language.

Section 2.3 exercises, pages 62-3.

• Exercise 3