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: We can use this recursive definition to give recursive definitions of the value of a positive decimal number as well as its digit sum.
    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.