1.) Let ={a, b}. Let F* be the set of all words over that end in the letter a and that do not contain immediate repetitions of b (there can be many occurrences of b, but they must be separated by at least one a) . For all n0 let F_n={wF | |w|=n}, i.e. the set of all words in the language F that are of length n.

Give a deterministic finite automaton accepting F

Give a regular expression describing F

Show that the cardinality of F_n is the n-th Fibonacci number: #F_n= fib(n), where fib(n) is defined through the recurrence:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n1) + fib(n2) n2