Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Fibonacci word
Summary
A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.
It is a paradigmatic example of a Sturmian word and specifically, a morphic word.
The name "Fibonacci word" has also been used to refer to the members of a formal language L consisting of strings of zeros and ones with no two repeated ones. Any prefix of the specific Fibonacci word belongs to L, but so do many other strings. L has a Fibonacci number of members of each possible length.
Let be "0" and be "01". Now (the concatenation of the previous sequence and the one before that).
The infinite Fibonacci word is the limit , that is, the (unique) infinite sequence that contains each , for finite , as a prefix.
Enumerating items from the above definition produces:
0
01
010
01001
01001010
0100101001001
The first few elements of the infinite Fibonacci word are:
0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ...
The nth digit of the word is where is the golden ratio and is the floor function . As a consequence, the infinite Fibonacci word can be characterized by a cutting sequence of a line of slope or . See the figure above.
Another way of going from Sn to Sn +1 is to replace each symbol 0 in Sn with the pair of consecutive symbols 0, 1 in Sn +1, and to replace each symbol 1 in Sn with the single symbol 0 in Sn +1.
Alternatively, one can imagine directly generating the entire infinite Fibonacci word by the following process: start with a cursor pointing to the single digit 0. Then, at each step, if the cursor is pointing to a 0, append 1, 0 to the end of the word, and if the cursor is pointing to a 1, append 0 to the end of the word.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.