Słowa Fibonacciego

Słowa Fibonacciego – ciąg słów stosowany w informatyce teoretycznej między innymi do analizy złożoności algorytmów tekstowych.

Definicja słów Fibonacciego

Słowa Fibonacciego są słowami nad alfabetem $\{a,b\}$ zdefiniowany rekurencyjnie jako:

$F_n:=\{\begin{array}{cc}b& \text{dla }n=1;\\ a& \text{dla }n=2;\\ F_{n-1}\cdot F_{n-2}& \text{dla }n>2.\end{array}$

Gdzie symbol $\cdot$ oznacza konkatenację.

Początkowe słowa Fibonacciego

$F_1=b$

$F_2=a$

$F_3=ab$

$F_4=aba$

$F_5=abaab$

$F_6=abaababa$

$F_7=abaababaabaab$

$F_8=abaababaabaababaababa$

$F_9=abaababaabaababaababaabaababaabaab$

Własności słów Fibonacciego

$|F_n|=f_n,$ gdzie $f_n$ jest $n$-tą liczbą Fibonacciego.

Niech $\tilde{w}$ oznacza słowo $w$ z ostatnimi dwoma literami zamienionymi kolejnością. Zachodzi:

$\widetilde{F_n}=F_{n-2}\cdot F_{n-1}$

Zobacz też

• słowo Thuego-Morse’a

Uwagi

Nie ma jednej konwencji dotyczącej oznaczania początkowych słów Fibonacciego. W niektórych źródłach przyjmuje się $F_0=b,$ $F_1=a,$ w innych z kolei $F_0=a,$ $F_1=ab.$

Alfabet $\{a,b\}$ nie jest konieczny (choć jest często używany). Można równie dobrze używać alfabetu $\{0,1\}$ lub innego dwuznakowego.

Bibliografia

• Szablon:Cytuj

Linki zewnętrzne

• Szablon:Otwarty dostęp Fibonacci word Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].