Q:

Is the language $L$ generated by 'Fibonacci Strings' (as given in the desciption) regular? If not, disprove by Pumping Lemma

The Fibonacci strings are defined as follows: $S_1=a$, $S_2=b$ and $S_k=S_{k-1}S_{k-2}$ for $k>2$ . For example $S_3=ba$ , $S_4=bab$ etc. Let $L$ be the language generated by the Fibonacci strings. Is the language $L$ regular?

A:

If the language is regular, then the pumping lemma guarantees that the set of lengths contains an arithmetic subsequence.
But the lengths of valid strings are the Fibonacci numbers, which grow exponentially.

