CSE 105 Assignment 1
Due: April 7, 1998 at the beginning of class
Read Chapter 1 (Hopcroft and Ullman).
Problems:
Problem 1:
Show the following statements by induction:
A: ((w^R)^R) = w
B: If v is a substring of w, then v^R is a substring of w^R
Problem 2:
What is wrong with the following purported proof that "All horses are the same color"?
Proof by induction on the number of horses:
Basis step: There is only one horse. Then clearly all horses are the same color.
Induction Hypothesis: In any group of up to n horses, all horses are the same color.
Induction Step: Consider a group of n+1 horses. Discard one horse; by the induction
hypothesis, all the remaining horses are the same color.
Now put that horse back and discard another horse; again, all remaining horses are the
same color. So all the horses are the same color as the ones that were not discarded either
time, and so they all are the same color.
QED
Problem 3:
Chapter 2, 2.4
Problem 4:
Chapter 2, 2.5 a-d
(Provide both the transition diagram and 5-tuple definition of your FSA).