Fibonacci strings are defined as follows:

F1 = "b", F2 = "a", and Fn = Fn-1Fn-2, (n > 2)

where the recursive rule uses concatenation of strings, so F2 is "ab", F3 is "aba". Note that the length of Fn is the nth Fibonacci number.

(a Prove that in any Fibonacci string there are no two b's adjacent and no three a's.
(b) Give the unoptimized and optimized ‘prefix' (fail) function for F7.
(c) Prove that, in searching for a Fibonacci string of length m using unoptimized KMP, it may shift up to phi(log m) times, where phi = (1+p5)/2, is the golden ratio. (Hint: Another way of saying the above is that we are given the string Fn and we may have to shift n times. Find an example text T that gives this number of shifts).
(d) What happens here when you use the optimized prefix function? Explain.