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

Assignment #2
Due Wednesday, 8 September 1999

Do the following exercises. Unless otherwise noted, the exercises are from the Linz textbook. Be sure to follow the directions concerning homework submission given in the class syllabus.

• String reverse can be defined as follows:
  1. 
  2. 
  Remember that string concatenation is associative and has as its identity element.

  Prove for all strings w and symbols a.

• Exercise 4 on page 27.

• Exercise 10 on page 27.

• Exercise 11, parts (b) and (d), on page 27.

• Exercise 1 on page 33

• Exercise 2 on page 33

• Exercise 9 on page 34

• Required for CSci 500 students, optional for CSci 311.
  Prove for all strings w.

  If applicable, you may use the results of the proof above.

UP to CSCI 311 assignments document? to CSCI 500?