Properties of Fibonacci languages

Abstract

The Fibonacci language F-u,F-nu is the set of all Fibonacci words, where the first word and the second word in the Fibonacci sequence are u and nu, respectively. We show that the language F-u,F-nu is context-free free. We also show that F-u,F-nu is not dense if the word u nu contains at least two distinct letters. Let w(i) denote the ith Fibonacci word. When considering the Fibonacci language F-a,F-b for two distinct letters a and b, we show that for k greater than or equal to 2 and 1 less than or equal to i < k, the word w(i)w(i) is not a prefix of the Fibonacci word w(k). We also show that for k greater than or equal to 2, the language F-k = {w(nk) / n greater than or equal to 1} is a code. (C) 2000 Elsevier Science B.V. All rights reserved.