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

Assignment #4
Due Friday, 29 September 2000 (Revised)

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 legibly on one side of the paper only, label each problem clearly, staple the papers in the proper order, and make sure your name is on the paper.

Give a regular expression for each of the following sets:

1. The set of strings of length two or more over {a,b} in which all the a's precede all the b's.

2. The set of strings over {a,b} that contain the substring aa and the substring bb.

3. The set of strings over {a,b} that do not contain the substring aaa.

Do the following exercises from the Linz textbook.

Section 3.1 exercises, pages 77-9.

• Exercise 14, part (d).
• Exercise 15, part (e)

Section 3.2 exercises, pages 88-90.

• Exercise 3
• Exercise 9, part (c)
• Exercise 13 (You may use Pascal, C, or Java real constants, but please identify what you are doing.)

Section 3.3 exercises, pages 99-100.

• Exercise 4
• Exercise 10, part (c)