Assignment 1
1. Use a direct method to prove that for any string x, xxR is palindromic.
2. Use no more than 8 cases to prove that every string of length 4 over the alphabet {a; b} contains a substring of the form xx, for some non-empty string x.
There are 16 possible strings, but you can use a decision tree to reduce the number of cases that you actually need to consider.
3. Recall the Fibonacci function dened by f (0) 0; f (1) 1;8n > 1; f (n) f (n ?? 1) + f (n ?? 2).
Use mathematical induction to show that for every n 2 N; f (n) (5=3)n.
4. For a nite language L, let |L| denote the number of strings in L. For example, |{; a; ababb}| 3.
The statement |L1L2| |L1||L2| says that the number of strings in L1L2 is equal to the product of |L1| and |L2|.
It turns out that this is sometimes, but not always, true. Find two distinct, nite languages L1; L2 {a; b} such that |L1L2| , |L1||L2|.