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

2012-04-26T14:03:15Z

91.122.183.63:

==Определение==
{{Определение
|definition='''Морфизмом''' называется отображение <tex>h</tex>, которое каждой букве <tex>\lambda</tex> из алфавита <tex>A</tex> ставит в соответствие строку <tex>h(\lambda)</tex> из множества <tex>A^{+}</tex>,
а каждой строке <tex>x</tex> из <tex>A^+</tex> ставит в соответсвие строку из <tex>A^+</tex> по следующему правилу :
<tex>h(x) = h(x[1])h(x[2])...h(x[n])</tex> , где <tex>x[1], x[2], \dots, x[n]</tex> уже являются элементами <tex>A</tex>.

}}

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

{{Определение
|definition='''Строками Фибоначчи''' являются строки, полученные последовательным применением морфизма <tex>h</tex> к строке <tex>x_0 = b</tex>, т.е. <tex>h^*(b)</tex>.
* <tex>A = \{a,b\}</tex>
* <tex>h(a) = ab</tex>
* <tex>h(b) = a</tex>

}}

Первые несколько строк Фибоначчи: 
* <tex>f_0 = b</tex>
* <tex>f_1 = a</tex>
* <tex>f_2 = ab</tex>
* <tex>f_3 = aba</tex>
* <tex>f_4 = abaab</tex>
* <tex>f_5 = abaababa</tex>

==Лемма==
{{Лемма
|statement= Строки Фибоначчи удовлетворяют рекуррентному соотношению <tex>f_n = f_{n-1}f_{n-2}, n \geq 2</tex>.
|proof=
Доказательство нетрудно получить методом математической индукции.

База. При <tex>n = 2</tex> равенство очевидно.

Переход. Пусть <tex>f_n = f_{n-1}f_{n-2}</tex>. <tex>f_{n+1} = h(f_n) = h(f_{n-1}f_{n-2})</tex>. Т.к. h {{---}} линейна (т.е. <tex>h(xy) = h(x)h(y)</tex>), то можно продолжить равенство.
<tex>f_{n+1} = h(f_{n-1})h(f_{n-2}) = f_{n}f_{n-1}</tex>
}}

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

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

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Основные определения. Простые комбинаторные свойства слов]]

Викиконспекты - Вклад участника [ru]

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