COSC 3410
                       Assignment #1
                Due: Friday, Sept. 10, 2010

1. For each of the following regular expressions, give three examples
of strings that match the expression and describe in words the set of 
strings matching the expression.

a) 1*0

b) 1*00*

c) (111)|(001)|(101)

d) (1|(00))*

e) 1*01*01*


2. Express each of the following sets using a regular expression.

a) the set of strings with one or more 0s followed by a 1
   = {01, 001, 0001, ...}

b) the set of 0,1-strings of two or more symbols followed by three or more 0s
   = {11000, 00000, 10010100000, ...}

c) the set of 0,1-strings of length four with exactly two 1s
   = {1100, 1010, 0110, ...}

d) the set of strings with an even number of 1s
   = {000, 0000, 11, 101, 01100101, 111111, ...}
   
e) the set of strings containing exactly three 0s
   = {000, 0011101, 1010101, 111000, 10111010111, ...}