Слово Фибоначчи

Определение

Определение:

Морфизмом называется отображение [math]h[/math], которое каждоый букве [math]\lambda[/math] из алфавита [math]A[/math] ставит в соответствие строку [math]h(\lambda)[/math] из множества [math]A^{+}[/math].

Отображение [math]h[/math] также распространяется на любую строку [math]x[/math] из множества [math]A^{+}[/math] путем использования следующего тождества:
[math]h(x) = h(x[1])h(x[2])...h(x[n])[/math].
Для полноты распространим отбражение на множество [math]A^{*}[/math], положив, что для любого морфизма [math]h(\epsilon) = \epsilon[/math].

Любой морфизм [math]h[/math] можно применять к исходной строке [math]x_0[/math] любое число раз, тем самым генерируя последовательность итераций [math]h^{*}(x_0)[/math] по следующему правилу:
[math]h^{*}(x_0) = \{h^0(x_0), h^1(x_0),...\}[/math].
где [math]h^0(x_0) = x_0[/math] и для любого целого [math]k \geq 1[/math] [math] h^k(x_0) = h(h^{k-1}(x_0))[/math].
Например:
[math]A = \{a,b\}, h(a) = a, h(b) = ab[/math].
[math]h^*(a) = \{a,a,...\}[/math]
[math]h^*(b) = \{b, ab, a^2b,..., a^kb...\}[/math]

Определение:

Строками Фибоначчи являются строки, порожденные следующим морфизмом: [math]A = \{a,b\}[/math] [math]h(a) = ab[/math] [math]h(b) = a[/math]

Свойства

Введем множество [math]h(f_0) = \{f_0, f_1,f_2,...\}[/math], где [math]f_n = h(f_{n-1})[/math] для любого целого [math]n \geq 1[/math], а [math]f_0 = b[/math].
Первые несколько строк Фибоначчи:

• [math]f_0 = b[/math]
• [math]f_1 = a[/math]
• [math]f_2 = ab[/math]
• [math]f_3 = aba[/math]
• [math]f_4 = abaab[/math]
• [math]f_5 = abaababa[/math]

Леммы

Лемма:

Строки Фибоначчи удовлетворяют рекуррентному соотношению [math]f_n = f_n-1 + f_n-2, n \geq 2[/math].

Доказательство:

[math]\triangleright[/math]

Доказательство нетрудно получить методом математической индукции. База. При [math]n = 2[/math] равенство очевидно. Переход. Пусть [math]f_n = f_{n-1} + f_{n-2}[/math]. [math]f_{n+1} = h(f_n) = h(f_{n-1} + f_{n-2})[/math]. Т.к. h - линейна (т.е. [math]h(x+y) = h(x) + h(y)[/math]), то можно продолжить равенство. [math]f_{n+1} = h(f_{n-1}) + h(f_{n-2}) = f_{n} + f_{n-1}[/math]

[math]\triangleleft[/math]

Также нетрудно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.

Литература

• Билл Смит Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус.)