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

Assignment #3
Due Thursday, October 1 (same day as Exam 1)

CSci 311 students do at least 10 of the following exercises. CSci 500 students do at least 11 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 5th edition of the Linz textbook.

Section 3.1 exercises, pages 75-7.

• Exercise 16, part (d).
• Exercise 17, part (e)

Section 3.2 exercises, pages 87-9.

• Exercise 4, part (b)
• Exercise 10, part (c)
• Exercise 15 (You may use real constants from C, Java, or other common languages, but please identify which language you are using. You may want to look up a formal syntax description in a manual.)

Section 3.3 exercises, pages 96-7.

• Exercise 1
• Exercise 6
• Exercise 13, part (c)
• Exercise 16