CSE 322 Assignment #1
Spring 2000

Due: Friday, April 7, 2000.

Reading assignment: Read Lewis and Papdimitriou sections 1.7 and 1.8.

Problems:

1. We usually write numbers in base 10. The language, L, of positive decimal numbers, is the set of strings over the alphabet SIGMA={0,1,2,3,4,5,6,7,8,9} that do not begin with 0. It is easy to see that L is exactly the set of strings generated by the following:
   • Any element of SIGMA other than 0 is a string in L
   • If x is in L then xa is in L for all a in SIGMA
   We can use this recursive definition to give recursive definitions of the value of a positive decimal number as well as its digit sum.
   • For each a in SIGMA, value(a)=a and digitsum(a)=a.
   • For each x in L and a in SIGMA, value(xa)=10*value(x)+value(a) and digitsum(xa)=digitsum(x)+digitsum(a).
   1. Give a regular expression representing L.
   2. Use modular arithmetic and induction on the definitions of value and digitsum to prove the `Rule of 3' which says that a number is divisible by 3 if and only if its decimal digits sum to a multiple of 3.

2. Argue that for any languages A, B, and C that A(B U C)= AB U AC (where I use U to denote union).

3. Lewis and Papadimitriou problem 1.8.3 page 51.

4. Lewis and Papadimitriou problem 1.8.5 page 52.

5. (Bonus) Find languages A, B, and C such that A (B ^ C) is not equal to AB ^ AC (where I use ^ to denote intersection).

6. (Bonus) Lewis and Papadimitriou problem 1.8.4 page 51. The wording here is confusing. Another way to write L' is as {w : There exists a string u such that uw in L}; i.e. this is the set of suffixes of the strings in L.