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

Question

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?

Answer 1

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.

Answer 2

Idea behind the pumping lemma:

$L$ is a regular language, thus $L$ can be recognized by a finite automaton. Such automaton has only a finite number of states. Recognition paths must traverse those states, thus for large words (with a length equal or greater than a critical length $p$) repetition must occur along the recognition path and thus within the string. One can avoid a repeated part or loop it arbitrary many times.

Formally the pumping lemma says:

If $L$ is a regular language there exists a $p \in \mathbb{N}_0$ with $p \ge 1$ such that for all $w \in L$ with $\lvert w \rvert \ge p$ we can split $w$ into $w = x y z$ with

1. $\lvert y \rvert \ge 1$
2. $\lvert xy \rvert \le p$ and
3. $x y^i z \in L \quad (i \in \mathbb{N}_0)$

If the Fibonacci strings $L = \{ S_i \mid i \in \mathbb{N} \}$ constitute a regular language then the above $p$ exists.

The Fibonacci strings have the property $\lvert S_n \rvert = F_n$, where $F_n$ is the $n$-th Fibonacci number $$ F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right) \to \frac{1}{\sqrt{5}} \left( 1.618\ldots \right)^n \quad (*) $$

The $F_n$ increase montonically for $n \ge 2$, so given $p$ we can find some $q$ with $F_q \ge p$. So for this Fibonacci string $w = S_q$ we can pump up part of the string and the resulting strings $S_q^{(i)}$ must be all Fibonacci strings: $$ S_q = w = x y z \in L \Rightarrow S_q^{(i)} = x\, y^i\, z \in L \quad (i \in \mathbb{N}) $$ We have $$ G_i = \lvert S_q^{(i)} \rvert = \lvert y \rvert \, i + \lvert x\rvert + \lvert z \rvert = s\, i + t $$ for some $s, t \in \mathbb{N}_0$, where $G_1 = F_q$, but which are different for the other $i$ from the $F_n$ from equation $(*)$ in general. The $F_n$ grow exponentially, the $G_i$ linear. They can have two points in common but not three. And for all $G_i$ there must be a $F_n$.

So $L$ can not be a regular language.

Answer 3

It is just a variation on Hagen von Eitzen's answer.

Let $S$ be your language and let $f: A^* \to \mathbb{N}$ be the monoid morphism defined by $f(u)= |u|$, where $|u|$ denotes the length of $u$. If $S$ is regular, then $f(S)$ is a rational subset of $\mathbb{N}$, that is, a finite union of arithmetic progressions. But $f(S)$ is the set of Fibonacci numbers and since $F_{n+1}-F_n$ tends to infinity, this set cannot contain an infinite arithmetic progression.