**$ 25.00**

**CS 311 Assignment 1 | Complete Solution**

**Smartwriter****Rating :**5**Grade :****A+****Questions :**4**Solutions :**163**Blog :**0**Earned :**$2757.55

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

**CS 311 Assignment 1 | Complete Solution**

- This solution has not purchased yet.
- Submitted On 11 Apr, 2015 01:49:45

**Smartwriter****Rating :**5**Grade :****A+****Questions :**4**Solutions :**163**Blog :**0**Earned :**$2757.55