CS326 - Assignment 2

Due Date: Friday, March 30, in class.

This is a written assignment due in class on Friday.

1. Start reading chapter 2 in the book.

2. Problem 3.6, p. 147.

3. Problem 3.7, all parts except (g), p. 147.

4. Problem 2.2, p. 78.

5. (Graduate) Prove that it is impossible to write a regular expression for the language

L = { an bn | n >= 0, where an is a string of n a's and bn is a string of n b's }.

Note: The language L is the set of strings { e, ab aabb, aaabbb, aaaabbbb, ... }.