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

Assignment #5
Due Monday, 4 October, 1999

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

Do the following exercises from the Linz textbook.

Section 4.1 exercises, pages 111-4.

• Exercise 2.
• Exercise 6. (Hint: Restate the right-hand-side in terms of operations on the language S_i.)
• Exercise 9.

Section 4.2 exercises, pages 116-7.

• CSCI 311 students: Exercise 2 or exercise 5.
• CSCI 500 students: Both exercises 2 and 5.

Section 4.3 exercises, pages 125-7.

• Exercise 4 (b) (c).
• Exercise 9 (a) (c) (f). If you answer "regular", show (or describe) a dfa or nfa to accept the language. It you answer "not regular", it is not necessary (but, of course, allowed) to give a formal proof. However, give a sentence or so to justify your answer.

UP to CSCI 311 assignments document?