Date: Tue, 10 Dec 1996 16:51:49 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 321 Assignment #5

CSE 321 Assignment #5
Autumn 1996

Due: Friday, November 1, 1996.

Reading Assignment: Read handout on induction proofs for recursively defined sets and sections 4.1-4.4 of the text. The following problems are from the Third Edition of the text.

Practice Problems: page 210, problem 31;

Problems:

  1. page 209, Problem 4.

  2. page 209, Problem 10.

  3. Give a recursive definition of the set of strings over alphabet A={a,b} that have an even number of a's. (You don't need to prove that it is correct.)

  4. Define a set of strings S by:

    Give a recursive proof that every string in S has exactly one more 1 than it has 0's.

  5. page 241, Problems 8, 12, and 20

  6. page 242, Problem 42. (A restriction to 8 character variable names is one reason why the names of all those Unix commands are so obscure.)

  7. (Bonus) page 242, Problem 48. (They just mean one column of the truth table.)

  8. (Bonus) page 249, Problem 20.