CS 311 Assignment 1 | Complete Solution

Cal Poly Pomona Computer Science Department
CS 311 Spring 2015

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|.