CS 3156 Section C, Fall 1998
Homework 2 -- due Friday, Oct. 9

1. Problem 1.12, page 85 of the text.

2. Problem 1.9, page 85 of the text.

3. Prove that the class of regular languages is closed under intersection. In other words, prove that if and are regular, then is regular. (Hint: use De Morgan's law.)

4. Problem 1.15, page 86 of the text.

5. Problem 1.13 (a,b,f,i,j), page 86 of the text.

Extra credit. Let be a language containing only strings of even length. The language is defined by

Informally, is the set of strings representing ``first halves'' of strings in L. Prove that, if L is a regular language containing only strings of even length, then is regular.