Theory of Computations 1. Prove that if S1 and S2 are finite sets with |S1| = n, and |S2| = m, then |S1 S2| n + m.

2. Let R be a relation such that for sets S1 and S2, (S1, S2) R if and only if |S1| = |S2|. Prove that R is an equivalence relation.

3. The relation x y if and only if x = y mod 3 is an equivalence relation. Use this equivalence relation to partition the set {1, 7, 12, 14, 15, 16, 19, 33, 34, 35} into equivalence classes.

4. How many substrings bba are there in wwRw, where w = aabbab?

5. Explain why there is no language L, such that (L*) = (L)*. Note: the apostrophe means complement.