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:
- page 209, Problem 4.
- page 209, Problem 10.
- 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.)
- Define a set of strings S by:
- 1 is in S
- If x is in S and y is in S then the string x0y is in S
- (And no other strings are in S)
Give a recursive proof that every string in S has exactly one more 1 than it
has 0's.
- page 241, Problems 8, 12, and 20
- 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.)
- (Bonus) page 242, Problem 48. (They just mean one column of the
truth table.)
- (Bonus) page 249, Problem 20.